4

ここで問題を説明します。

1000単語のリストがあるとします。辞書だと言う。ユーザーはいくつかの単語を入力し、その単語が正しい場合、または最も近い一致を与える場合、完全一致と一致します。Google 検索と同じように、何かを入力すると、最も近い一致が表示されます。

私が考えたアルゴリズムは

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. それ以外の場合は、要求された単語と隣接する単語およびその近傍 (定義される) とのレーベンシュタイン距離を計算し、それらを戻り値のリストに追加します (満足している場合)。
  5. 選択された隣接する単語のリストを返します

を使用した迅速で汚い実装/usr/share/dict/words(まだレーベンシュタイン距離の部分と選択を行う必要があります)

免責事項: 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

この種の「ファジー」単語検索の一般的なアルゴリズムは、レーベンシュタイン距離です。実際に似ている単語を見つけるのではなく、単語の類似度を計算します。この類似性スコア (またはレーベンシュタイン距離) は、類似した単語を選択するために、並べ替えまたはフィルター関数で使用できます。

距離の測定方法は単純です。ターゲットの単語から一致した単語に変更する必要がある文字の数です。たとえば、距離 3 は、単語間の違いが 3 編集であることを意味します (文字の追加と削除の操作も含まれるため、必ずしも文字ではありません)。

Rosetta Code サイトには、tcl や perl などのさまざまな言語で実装されたレーベンシュタイン距離アルゴリズムのリストがあります: http://rosettacode.org/wiki/Levenshtein_distance

tcler の wiki には、レーベンシュタイン距離のいくつかの実装を含む類似度アルゴリズムについて説明しているページがあります。

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 に答える