一种有效的算法,用于处理将唯一单词保存到文件


an efficient algorithm to handle saving unique words to a file

我目前所做的是,从URL解析文本,然后清理文本并按空格分解并保存到文件中。

我发现困难的是,

仅保存唯一文件,以防抓取多个 url:

案例:从 site.com/page1 中抓取单词并将唯一的单词保存到文件中。抓取 site.com/page2 时,我需要检查每个单词是否已经在文件中,并仅在不存在时才保存它。

我的想法是,取 $word[0],然后从文件中获取每一行,如果未找到,请检查并保存。但这就像数千到数十万次的迭代。

我不是在寻找任何代码,而只是知道如何高效快速地处理它。

我假设您已经将从 site1 获得的唯一单词存储在名为 site1.txt 的文件中,并且您已经在名为 $site2 的数组中从 site2 中抓取单词,现在您想将$site2逐行存储在文件site2.txt中,仅存储唯一的单词:

$wordsInFile1 = file('site1.txt');
$wordsInFile1 = array_flip($wordsInFile1);
foreach($site2 as $i => $word) {
    if(isset($wordsInFile1[$word])) {
       unset($site2[$i]);
    }
}
// now $site2 contains unique words from site2 and words that are not in site1.txt

我所知,您当前的算法在复杂度类O(n^2)中。你为每个单词再次迭代列表,这不太好,对吧。我建议您首先将所有单词写入文件,然后使用有效的算法对列表进行排序。完成此操作后,您可以删除重复项。例如,在 linux 下,您可以使用以下命令:

sort -u unsortedList > sortedAndCleanedList
grep <word> file应该

工作得很快

或者,您可以创建一个名为单词的 md5 的空文件,然后在将单词添加到主文件之前检查 md5(word) 文件是否存在。请注意,某些文件系统不允许目录中超过 32767 个文件(因此您可能需要根据 md5 哈希的前几个字符创建子目录)

您可以使用允许快速搜索的内存中表示形式(如哈希表)高效快速地处理它。

假设你有一个函数,它返回文件中的所有单词,规范化,不标点,没有空格:

$words = extract_words('Hello my dear!');

其中$words的结果是:

array(
    'hello' => 1,
    'my'    => 1,
    'dear'  => 1,
);
您可以使用以下方法

var_export将此哈希表快速存储到文件中:

$file = 'words1.txt';
file_put_contents(sprintf('return %s;', var_export($words, TRUE)));

并使用include重新阅读:

$words = include($file);

要检查该哈希图是否包含该单词,请使用isset

$exist = isset($words[$word]);

由于这里有数组,您可以跨文件合并它们,比较它们等 - PHP 有许多基于数组的函数可用。如果你想用PHP来做,我认为这是非常快的。

如果你有更大的列表,我建议你使用通常用于通常用 C 编写的几 GB 单词列表的工具。

您可以对文件进行排序,然后搜索单词。

想法是保持文件排序,然后使用任何搜索算法在文件中查找具有相同模式的现有条目。如果找不到现有条目,请插入新条目。

保持文件排序的成本需要硬盘操作。