我会在这里解释一下这个问题.
假设我有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
我知道这是漫长的道路,需要很多时间.有谁知道如何实现更好的算法
解决方法
>对数组中的单词进行排序
>当一个单词进来时=>二进制搜索(log(n))(我们正在这样做,因为如果你使用哈希表,它将对直接匹配有好处,但对于相邻则很差)
>如果完美匹配则返回
>否则使用相邻的单词及其邻居(待定义)计算所请求单词的 levensthein distance,并将它们添加到返回列表中(如果它们满足)
>返回所选相邻单词的列表
>当一个单词进来时=>二进制搜索(log(n))(我们正在这样做,因为如果你使用哈希表,它将对直接匹配有好处,但对于相邻则很差)
>如果完美匹配则返回
>否则使用相邻的单词及其邻居(待定义)计算所请求单词的 levensthein distance,并将它们添加到返回列表中(如果它们满足)
>返回所选相邻单词的列表
使用/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,$target) < 0;
while (1)
{
my $mid = int (($posmin + $posmax) / 2);
my $result = &$cmp ($mid,$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字
哪个单词是您要搜索的单词.