4

我将在这里解释问题。

假设我有 1000 个单词的列表。说它是一本字典。用户将输入一些单词，如果单词正确或给出最接近的匹配，它将与完全匹配匹配。就像谷歌搜索一样，当我们输入一些东西时，它会给出最接近的匹配。

我认为的算法是

Read the word list one by one
split our input word string into characters
take the first word from the list and match character wise
similarly do it for other words in the list

我知道这是一条很长的路，需要很多时间。有谁知道如何实现更好的算法

4

3 回答 3

5
  1. 对数组中的单词进行排序
  2. 当一个词进入 => 二进制搜索 (log(n)) 时（我们这样做是因为如果你使用哈希表，它对直接匹配有好处，但对相邻却很差）
  3. 如果完美匹配返回它
  4. 否则计算所请求单词与相邻单词及其邻居（待定义）的leventhein 距离，并将它们添加到返回列表（如果它们令人满意）
  5. 返回选中的相邻单词列表

快速而肮脏的实现/usr/share/dict/words（你仍然需要做 levensthein 距离部分和选择）

免责声明：从http://www.perlmonks.org/?node_id=503154借用的二进制搜索代码

open(FILE, "<", "/usr/share/dict/words");
my @lines = <FILE>;
my $word = $ARGV[0];

sub BinSearch
{
    my ($target, $cmp) = @_;
    my @array = @{$_[2]};

    my $posmin = 0;
    my $posmax = $#array;

    return -0.5 if &$cmp (0, \@array, $target) > 0;
    return $#array + 0.5 if &$cmp ($#array, \@array, $target) < 0;

    while (1)
    {
        my $mid = int (($posmin + $posmax) / 2);
        my $result = &$cmp ($mid, \@array, $target);


        if ($result < 0)
        {
            $posmin = $posmax, next if $mid == $posmin && $posmax != $posmin;
            if ($mid == $posmin){
                return "Not found, TODO find close match\n";
            }
            $posmin = $mid;
        }
        elsif ($result > 0)
        {
            $posmax = $posmin, next if $mid == $posmax && $posmax != $posmin;
            if ($mid == $posmax){
                return "Not found, TODO find close match\n"; 
            }
            $posmax = $mid;
        }
        else
        {
            return "Found: ".@array[$mid];
        }
    }
}
sub cmpFunc
{
    my ($index, $arrayRef, $target) = @_;
    my $item = $$arrayRef[$index];
    $item =lc($item);
    $target =lc($target);
    $a =  $item cmp $target;
    return $a;
}

print BinSearch($word."\n", \&cmpFunc, \@lines)."\n";

用法（如果调用脚本find_words.pl）：

perl find_words.pl word

其中 word 是您要搜索的单词。

于 2013-09-19T06:55:00.823 回答
4

这种“模糊”单词搜索的常用算法是Levenshtein distance。它并没有真正找到相似的单词，而是计算单词的相似度。这个相似度得分（或 Levenshtein 距离）然后可以被排序或过滤函数用来选择相似的词。

如何测量距离很简单：从目标词到匹配词需要改变多少个字符。例如，距离为 3 表示单词之间的差异是 3 次编辑（不一定是字符，因为它还包括添加和删除字符的行为）。

Rosetta Code 网站列出了用各种语言（包括 tcl 和 perl）实现的 Levenshtein 距离算法：http ://rosettacode.org/wiki/Levenshtein_distance

tcler 的 wiki 上有一个页面讨论相似度算法，其中包括 Levenshtein 距离的几种实现：相似度

对于 perl，还有一个可以使用的 CPAN 模块：Text::Levenshtein

所以在 perl 中你可以简单地做：

use Text::Levenshtein;

my %word_distance;
@word_distance{@dictionary} = distance($word,@dictionary);

然后遍历word_distance哈希以找到最相似的单词。

于 2013-09-19T07:20:57.427 回答
2

使用简单的二分搜索来获得相似词的邻域，然后使用 Levenshtein 算法进行细化的问题在于，错误可能出现在单词的早期和后期；如果出现早期错误，您将冒着完全漏掉单词的风险。一种更有效的技术可能是使用 Soundex 算法在您的单词列表中创建归类键，以便您按基本相似性进行搜索。然后，您可以使用 Levenshtein 进行细化，但通过基础源语料库中单词的稀有度来加权相似性度量；假设用户更可能想要一个常用词而不是一个稀有词是一种有用的衡量标准。（这假设你有一个源语料库，但如果你想模仿谷歌，那么你肯定必须有一个。）

最好转而研究使用某种 map-reduce 机制在整个单词集上运行加权 Levenshtein 距离度量的方法。这更像是一种“将硬件扔到问题上”的方法，但避免了与由于初始过滤器而丢失单词的潜在问题相关的问题。唉，这确实意味着你最终会得到一些无法作为简单软件的一部分推送的东西（提供系统来支持这样的东西不太可能是你想要强加的东西普通用户），但部署在服务后面可能是实际的。

于 2013-09-19T09:15:03.387 回答