3

PHP プロジェクトでこの問題を解決する必要があります。この問題では、一部のキーワード (数百から数千まで、長さはさまざま) を 100 ～ 300 文字の長さ、場合によっては 30 ～ 50 文字の短い文字列で検索する必要があります。検索文字列の新しいインスタンスを再利用するために、キーワードを前処理できます。私はPHPが初めてで、PHPライブラリでこれを行う方法が見つかりませんでした。少し検索したところ、Aho Corasick アルゴリズムでいくつかの適切な候補が見つかりました。次に、Sun Wu と Udi Manber によるこの改善は、agrep としても知られている (または agrep の一部である) ようです: http://webglimpse. net/pubs/TR94-17.pdf

Rabin Karp や Suffix Trees などもありますが、最初は固定長のキーワード用で、後者は非常に汎用的でかなり多くの作業が必要になるため、あまり適していないように見えました。

Agrep/Sun Wu-Manber を PHP で自分で実装することがこの問題を解決する良い方法であるかどうか、誰か教えてもらえますか? 別のフィードバックはありませんか？

編集: 以下のコメントで述べたように、何百もの異なる検索キーワードがあるため、正規表現は役に立ちません。したがって、その応答は役に立ちません。

4

2 に答える 2

1

「レーベンシュタイン距離」メトリックを使用すると、この問題を解決できると思います。

ウィキペディアから;

情報理論とコンピューター サイエンスでは、レーベンシュタイン距離は、2 つのシーケンス間の差の量を測定するための文字列メトリックです。

さらに、PHP にはレーベンシュタイン() メソッドがあります。キーワードリストを配列として使用し、検索可能な文字列を入力として使用し、配列を反復処理し、各反復で levenshtein() を使用して一致させます。

于 2012-06-15T15:38:48.547 に答える
0

PHP 5.5 以降、PHPstrtrはマルチパターン マッチングに Wu-Manbers アルゴリズムを使用します。実装の詳細については、PHP git リポジトリのcommit ccf15cf2を参照してください。私の経験では、それは非常に効率的です。

Aho-Corasick アルゴリズムの純粋な PHP 実装は、https ://packagist.org/packages/wikimedia/aho-corasick から入手できます。

于 2015-06-15T05:48:27.370 に答える