perl – 需要一种算法来创建像搜索一样的谷歌

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,并将它们添加到返回列表中(如果它们满足)
>返回所选相邻单词的列表

使用/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 matchn";
            }
            $posmin = $mid;
        }
        elsif ($result > 0)
        {
            $posmax = $posmin,next if $mid == $posmax && $posmax != $posmin;
            if ($mid == $posmax){
                return "Not found,TODO find close matchn"; 
            }
            $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字

哪个单词是您要搜索的单词.