17

あいまい一致に関する多くのリンクを見つけ、ある文字列を別の文字列と比較して、どれが最も高い類似度スコアを取得するかを確認しました。

ドキュメントである 1 つの非常に長い文字列と部分文字列があります。部分文字列は元のドキュメントから取得されたものですが、何度か変換されているため、スペースやダッシュなどの奇妙なアーティファクトが導入されている可能性があります。部分文字列は、元のドキュメントのテキストのセクションと 99% 以上一致します。この文字列がどのドキュメントからのものかを確認するために一致していません。文字列が始まるドキュメント内のインデックスを見つけようとしています。

ランダム エラーが発生しなかったために文字列が同一である場合は、 を使用document.index(substring)しますが、文字の違いが 1 つでもあると失敗します。

文字列と部分文字列の両方で az を除くすべての文字を削除し、比較してから、文字列を圧縮したときに生成したインデックスを使用して、圧縮された文字列のインデックスを実際のドキュメントのインデックスに変換することで、違いが説明されると思いました. これは、違いが空白と句読点である場合はうまく機能しましたが、1文字が異なるとすぐに失敗しました.

ドキュメントは通常、数ページから 100 ページであり、部分文字列は数文から数ページです。

4

5 に答える 5

5

あなたはマッチを試すことができます。これは ruby​​ gem として入手できます。私は長い間ファジー ロジックを扱っていませんが、必要なものは揃っているようです。amatch のホームページはhttp://flori.github.com/amatch/です。

退屈してアイデアをいじくり回すだけで、完全に最適化されておらず、テストされていないソリューションのハックが続きます。

include 'amatch'

module FuzzyFinder
  def scanner( input )
    out = [] unless block_given?
    pos = 0
    input.scan(/(\w+)(\W*)/) do |word, white|
      startpos = pos
      pos = word.length + white.length
      if block_given?
        yield startpos, word
      else
        out << [startpos, word]
      end
    end
  end

  def find( text, doc )
    index = scanner(doc)
    sstr = text.gsub(/\W/,'')
    levenshtein = Amatch::Levensthtein.new(sstr)
    minlen = sstr.length
    maxndx = index.length
    possibles = []
    minscore = minlen*2
    index.each_with_index do |x, i|
      spos = x[0]
      str = x[1]
      si = i
      while (str.length < minlen)
        i += 1
        break unless i < maxndx
        str += index[i][1]
      end
      str = str.slice(0,minlen) if (str.length > minlen)
      score = levenshtein.search(str)
      if score < minscore
        possibles = [spos]
        minscore = score
      elsif score == minscore
        possibles << spos
      end
    end
    [minscore, possibles]
  end
end

明らかに、多くの改善が可能であり、おそらく必要です! 上からいくつか：

  1. ドキュメントを一度処理し、結果をデータベースに保存します。
  2. 最初のチェックに使用できる文字列の長さを決定し、最初の部分文字列に対して処理を行ってから、フラグメント全体の照合を試みます。
  3. 前に続いて、その長さの開始フラグメントを事前に計算します。
于 2011-05-23T08:44:17.147 に答える
2

ここで詳しく説明されている StrikeAMatch の実装を確認する必要があります: 可変長文字列のより良い類似性ランキング アルゴリズム

ある種の文字列距離 (つまり、2 つの文字列間の変更の数) に依存する代わりに、これは文字ペアのパターンを調べます。各文字列に出現する文字のペアが多いほど、一致度が高くなります。私たちのアプリケーションでは、プレーン テキスト ファイルで入力ミスや可変長の見出しを検索するのに非常に役立ちました。

StrikeAMatch (文字レベルのバイグラムでのDice の係数の実装) とレーベンシュタイン距離を組み合わせて一致を見つける gem もあります: https://github.com/seamusabshere/fuzzy_match

于 2013-08-22T10:31:33.173 に答える
1

それは、部分文字列になる可能性のあるアーティファクトに依存します。それらが一部ではない単純なケースでは、部分文字列を解析してからドキュメントで[a-z]使用できます。Regexp#match

document = 'Ulputat non nullandigna tortor dolessi illam sectem laor acipsus.'
substr = "tortor - dolessi _%&#   +illam"

re = Regexp.new(substr.split(/[^a-z]/i).select{|e| !e.empty?}.join(".*"))
md = document.match re
puts document[md.begin(0) ... md.end(0)]
# => tortor dolessi illam

(ここでは、正規表現に括弧を設定していないため、 の最初の (完全一致) 要素でbeginandを使用します。end0MatchData

開始位置のみに関心がある場合は、=~演算子を使用できます。

start_pos = document =~ re
于 2011-05-23T07:07:00.280 に答える
-2

私はそれらのどれも使用していませんが、で「diff」を検索するだけでいくつかのライブラリが見つかりましたrubygems.org。それらはすべてgemでインストールできます。あなたはそれらを試してみたいかもしれません。私自身も興味があるので、すでに知っている方や試してみた方は、コメントを残していただければ助かります。

于 2011-05-23T07:53:29.197 に答える