29

正規表現を使用してあいまい一致を行う方法を探しています。私はPerlを使いたいのですが、誰かがこれを行う方法を推奨できるなら、それは役に立ちます.

例として、「New York」という単語の前に 2 桁の数字が続く文字列を一致させたいとします。テキストがPDFのOCRからのものであるため、難しさが生じます。そのため、あいまい一致を実行したいと考えています。一致させたい:

12 New York
24 Hew York
33 New Yobk

およびその他の「近い」一致 (レーベンシュタイン距離の意味で)。

aa New York
11 Detroit

明らかに、一致の許容距離 (「あいまいさ」) を指定する必要があります。

私が理解しているように、これを行うために Perl モジュールを使用することはできませんString::Approx。なぜなら、一致に正規表現を含める必要があるためです (前の数字と一致させるため)。

また、これは私が実際に一致させようとしているものの非常に単純化された例であるため、力ずくのアプローチを探しているわけではないことに注意してください。

追加するために編集：

さて、私の最初の例は単純すぎました。人々が前の数字にこだわるつもりはありませんでした -- 悪い例で申し訳ありません。これがより良い例です。次の文字列を検討してください。

ASSIGNOR, BY MESHS ASSIGN1IBNTS, TO ALUSCHALME&S MANOTAC/rURINGCOMPANY, A COBPOBATlOH OF DELAY/ABE.

これが実際に言っていることは次のとおりです。

ASSIGNOR, BY MESNE ASSIGNMENTS, TO ALLIS-CHALMERS MANUFACTURING COMPANY, A CORPORATION OF DELAWARE

私がする必要があるのは、「ALUSCHALME&S MANOTAC/rURINGCOMPANY」と「DELAY/ABE」というフレーズを抽出することです。(これは狂気のように思えるかもしれませんが、私は楽観主義者です。) 一般に、パターンは次のようになります。

/Assignor(, by mesne assignments,)? to (company name), a corporation of (state)/i

マッチングが曖昧です。

4

10 に答える 10

17

テキスト コレクションに対して最適な一致を見つけたいパターンが 1 つある場合は、 q-gram distanceを試すことができます。特別なニーズに合わせて実装および採用するのは非常に簡単です。

パターンとテキストはかなり長いはずなので、2番目の説明は実際にここで役に立ちました. q-gram距離は「York」などの単語ではうまく機能しませんが、典型的なパターンが住所全体である場合は問題ありません。

次のようにしてみてください。

  • テキストとパターンを縮小文字セットに変換します。たとえば、大文字のみ、ストリッピング、単語化 (単語間に 1 つのスペース) など、すべての記号を "#" などに置き換えます。
  • 作業する q-gram の長さを選択します。3 つまたは 2 つ試してください。これを と呼びますq=3。
  • それよりも、各テキストのqgram-profileを作成します:
  • 各テキストをq単語に分割します。NEW_YORKとなり[NEW, EW_, W_Y, _YO, ORK]、各テキストと一緒に保管してください。
  • パターンを検索する場合は、パターンで同じことを行います。
  • text-qgram-database をループして、
    • 各パターン/テキストのペアを数えます-いくつのqgramが同じですか。
    • ヒットごとにスコアが 1 ずつ上がります。
  • スコアが最も高いテキストがベストヒットです。

それを行った場合、次の方法でこのアルゴリズムを微調整できます。

  • すべてのテキスト (および検索前のパターン) のq-1先頭に特別な文字を追加すると、短い単語でも適切なプロファイルが得られます。例えばNew York​​になり^^NEW YORK$$ます。
  • すべての子音を "x" に、母音を "o" に置き換えるなど、いろいろ試してみることもできます。このようにいくつかの文字クラスをいじったり、文字のグループを互いに置き換えてスーパーシンボルを作成することもできます。つまり、 CKがKになったり、SCHが$になったりします。
  • qgram-hit でスコアを上げると、text と patternの長さの違いなど、他のことで 1 の値を調整できます。
  • 2 グラムと 3 グラムの両方を保管し、数える場合は別の重さを量ります。

O(|T|*|P|)ここで説明されている基本的な形式のこのアルゴリズムは、検索中、つまり(テキスト|T|とパターン|P|の合計の長さを使用して)実行時間が長くないことに注意してください。これは、すべてのテキストをループしてから、パターンをループすると説明したためです。したがって、これは中規模のテキストベースでのみ実用的です。少し考えれば、q-gram に対して高度なインデックス構造を作成できるので (おそらくハッシュテーブルを使用して)、これは巨大なテキストベースにも実用的です。

于 2010-11-21T12:55:03.500 に答える
3

Web1T5グラムバージョン1のようなものと条件付き尤度最大化アプローチを使用してみることができます。

正しく思い出せば、Beautiful Dataの第14章では、このデータセットと、それを使用してスペルミスなどを見つける方法について説明しています。

于 2010-11-11T15:46:25.137 に答える
3

Jarkko の String::Approxモジュールを CPAN で使用することを検討しましたか? アルゴリズムが組み込まれてagrepいますが、Udi のものよりもはるかに低速です。

于 2010-11-19T05:14:46.963 に答える
3

正規表現には特定のルールがあり、必要なことを行うために構築されていません。2 つのパスを作成する方がはるかに簡単になります。正規表現を使用して数字を取り除き、モジュールを使用して一致を近づけます。

このようなもの（入力がファイルからの行であると仮定）

while( my $line = <$fh> ) {
    chomp $line;

    # do we have digits?
    if( $line =~ /^\d+/ ) {
         # removes spaces and digits from the beginning of the line
         $line =~ s/^[\d\s]*//g;

         # use your module to determine if you have a match in the remaining text.
         if( module_match ) {
             # do something
         }
         else {
             #no match
         }
    }
    else {
        # no match
    }
}
于 2010-11-11T15:20:11.213 に答える
2

経験則：Stack Overflowに移動して、「単一の正規表現でXを実行するにはどうすればよいですか？」と尋ねる必要がある場合。1つ以上の正規表現でXを実行することを検討する必要があります。

あなたの編集に基づいて、私はこのようなことをします：

while(<>) {
  chomp;
  if(/assignor, by (\w+) (\w+), to (\w+), a (\w+) of (\w+)/i) {
    # now use String::Approx to check that $1, $2, $3, $4, and $5 match
  } else {
    warn "Errors!\n";
  }
}

ここですべてを提供するわけではありません。正規表現を単純化するためにビットをオプションにしなかった", by (\w+) (\w+)"ので、その要点を理解できます。(?:)そのためには、おそらく名前付きキャプチャと非キャプチャグループに頼る必要があります。私はそのすべてを掘り下げる気にはなれませんでした。私がこれにどのように取り組むかをあなたが理解するのを手伝いたかっただけです。

覚えておいてください：「1つの正規表現ですべてを行うにはどうすればよいですか？」単一の正規表現ですべてを実行しようとするのはやめるべきです。

于 2010-11-15T01:40:13.313 に答える
2

で候補をText::Levenshtein絞り込んで編集距離を取得し、制限と比較して grep することができます。

しかし、別のアイデアは、正しい形式を取り、適切な形式を指すヒヤリハットからキー付けされたハッシュを作成して、それらも候補になる可能性があるということです。

正規表現の場合、おそらく次のような実験的なコードセクションを使用する必要があります。

m/ (?i: [new] | \p{Alpha} (?{ $misses++ }) ){2,4}
   \s+
  (?i: [york] | \p{Alpha} (?{ $misses++ }) ){3,5}
 /x

この場合、おそらく適切な値ごとに正規表現が必要になるでしょう。ターゲットを逃したことを示すフラグが必要になるでしょう。

于 2010-11-11T15:23:41.327 に答える
2

正規表現を使用して の要件を適用し[0-9]{2,2} (.*)、残りのテキストをキャプチャしてあいまい一致を実行する 2 段階のテストを検討しましたか? 問題を正規表現とファジー文字列の交差と考えてみてください。

于 2010-11-11T15:20:05.037 に答える
2

問題を 2 つの部分に分けます。

  1. 2 桁の数字を一致させます。
  2. 剰余を 'New York' とあいまいに一致させます。

この例では、'New York' が 2 つの単語で構成されていることがわかります。それを活用して、「デトロイト」(必ずしも「サンフランシスコ」とは限りません) などの代替をより簡単に排除できる場合があります。

結局のところ、 「 String::Approx 」を使用することさえできるかもしれませんが、次のように述べています。

... CPAN の Text::Levenshtein および Text::LevenshteinXS モジュール。Text::WagnerFischer と Text::PhraseDistance も参照してください。

(私の Perl は CPAN 経由で Text::PhraseDistance を見つけることができませんでした - 他のものは利用可能で、インストールもOKです。)

于 2010-11-11T15:20:39.107 に答える
1

perl を指定しましたが、レーベンシュタイン編集距離を実装する便利なアルゴリズムが R に組み込まれています。

agrep()

このコマンドでは、一致する正規表現またはパターンを使用することもできます。見ることをお勧めします。http://stat.ethz.ch/R-manual/R-devel/library/base/html/agrep.html

于 2010-11-19T05:09:12.580 に答える