0

レベンスタイン距離や文字列シメトリクスのさまざまなソリューションのライブラリなどのよく知られたアルゴリズムのいくつかを使用して、2 つの文字列 (製品名) を比較しようとしています ( SmithWatermanGotoh algで最良の結果が得られました)。

2 つの文字列は次のとおりです。

iPhone 3gs 32GB ブラック

Apple iPhone 3 gs 16GB ブラック

一部の単語の順序が異なる場合 (アルゴリズムの動作から予想される)、Levenstein は文字列全体でかなりうまく機能しないため、単語ごとの比較を実装しようとしました。

私が直面している問題は、スペース char (' 3gs '->' 3 gs ' ; ' 32 GB '->' 16GB ') で区切られた類似の「単語」を検出する方法です。

私のコードは、短い (単語数、== の場合は str.length) 文字列を長い文字列と比較します。単語は に分割されArrayList<String>ます。str1 の各単語を同じ文字列内の他の単語と組み合わせて、新しい配列リストを作成しています。

大まかなコードは次のとおりです。

foreach(str1)

    foreach(str2)
        res1 = getLevensteinDist
    endforeach

    foreach(combinedstr2)
        res1 = getLevensteinDist
    endforeach      

    return getHigherPercent(res1, res2)

 endforeach

これは、str2 の単語が分割されている場合に機能しますが、逆の方法がわかりません。str1 で分割されている str2 の単語を検出します。

私が何をしようとしているのか、少なくとも少しは明確になっていることを願っています。すべての助けに感謝します。

4

4 に答える 4

1

まず、文字列を前処理する必要があります。つまり、入力文字列から「a、the、as、an」とすべての一般的な動詞、数字などを削除する必要があります。また、すべての複数形を単数形に変換する必要があります。 ...すべての単語を統一する。次に、いくつかの文字列一致アルゴリズムを適用するか、単に単語をハッシュマップに入れるか、単語が多い場合はそれらをトライに入れ、類似度アルゴリズムを実行します。

于 2013-08-23T10:13:14.813 に答える
0

13 年前、私は "Wilbur-Khovayko アルゴリズム" という名前のトライグラム ファジー検索アルゴリズムの独自の実装を作成しました。

ここからダウンロードできます: http://olegh.cc.st/wilbur-khovayko.tar.gz

入力された検索語に対して「最も近い N 語」を検索します。

用語のリスト - ファイル termlist.txt 内 N - 変数 lim 内、ファイル findtest.c

アルゴリズムは非常に高速です。古い Sun 200mHz では、100,000 エントリの中から最も近い 100 語を約 0.3 秒間検索します。

于 2013-08-24T00:58:51.073 に答える