50

私の仕事では、ダメラウ・レーベンシュタイン距離などの近似文字列マッチングアルゴリズムを使用して、コードがスペルミスの影響を受けにくくするという素晴らしい結果が得られました。

ここで、文字列をのような単純な正規表現と照合する必要がありますTV Schedule for \d\d (Jan|Feb|Mar|...)。これは、文字列TV Schedule for 10 Janが0をT Schedule for 10. Jan返し、2を返す必要があることを意味します。

これは、正規表現（この場合は100x12）ですべての文字列を生成し、最適な文字列を見つけることで実行できますが、実用的ではありません。

これを効果的に行う方法について何かアイデアはありますか？

4

6 に答える 6

27

正規表現のあいまい一致を正確に行うことができるように見えるTREライブラリを見つけました。例: http://hackerboss.com/approximate-regex-matching-in-python/ ただし、挿入、削除、置換のみをサポートしています。転置なし。しかし、それはうまくいくと思います。

次のファイルの正規表現を使用して、付属の agrep ツールを試しました。

TV Schedule for 10Jan
TVSchedule for Jan 10
T Schedule for 10 Jan 2010
TV Schedule for 10 March
Tv plan for March

そして得た

$ agrep -s -E 100 '^TV Schedule for \d\d (Jan|Feb|Mar)$' filename
1:TV Schedule for 10Jan
8:TVSchedule for Jan 10
7:T Schedule for 10 Jan 2010
3:TV Schedule for 10 March
15:Tv plan for March

ご提案いただきありがとうございます。

于 2010-03-04T10:54:24.653 に答える
9

参照: Python 正規表現 (新しいバージョン、2014 年 10 月) (ドキュメント内で「fuzzy」を検索してください)。

あなたが Python の専門家でない場合 (私もそうではありません)、コードを C (exe/dll) にコンパイルできます。そうすれば、古き良きvb6（など）からでもdllを使用できるようになります。

選択できるその他のライブラリ:

  • TRE/agrep ('classic, good, old and fast) ('agrep performace' で検索)、ただし、POSIX 互換の正規表現を記述する必要があります ('regular expressions info posix' で検索)。この制限 (「Python での hackerboss 近似正規表現マッチング」を検索してください)。大量のデータの場合: 「agrep アルゴリズムの高速 CUDA 実装」を検索します。
  • FREJ (Java) - いくつかの (その他の) 制限 (たとえば、先読み/後読みなし)
  • fuzzy-wuzzy (Python ベース) - 一見の価値はありますが、テストされていません...

次も検索:

  • 「Comparison_of_regular_expression_engines」
  • 「regular-expressions.info ツール」

（本当のリンクを投稿できなくてごめんなさい）

于 2014-10-26T23:23:53.847 に答える
3

これは、あなたが尋ねている質問に関するリソースです。それは会社にとってちょっとしたティーザーです。もっと役立つのは、この論文です。大規模なデータセットに対して、特別な言語 (アラビア語と英語など) に偏ったあいまい検索を実行できる、論文に触発された実装を見たことがあります。

一般に、あなたが尋ねたことを行うことはできません。文字を等価クラスに置き換えることで正規表現検索をあいまいにするか、レーベンシュタイン距離によって定義された近似一致をデータベースで検索できます。(n)DFA を正規表現の後ろに拡張して距離に近い一致を含めようとすると、急速に信じられないほど複雑になります。

于 2010-02-28T16:33:06.267 に答える
1

lexerの使用を検討しましたか?

私は実際に使用したことがないので、あまり参考にはなりませんが、合いそうです！

于 2010-02-28T16:18:47.827 に答える