25

あいまい一致とは、レーベンシュタイン距離などによる類似の文字列を意味するのではなく、TextMate/Ido/Icicles で使用される方法です。間の文字、最適な適合を優先します。

4

6 に答える 6

31

私はあなたが探していたものをついに理解しました。この問題は興味深いですが、あなたが見つけた2つのアルゴリズムを見ると、仕様について人々が大きく異なる意見を持っているようです;)

問題と要件をより明確に述べると役立つと思います。

問題:

ユーザーが実際に意図したキーワードの数文字だけを入力し、選択するリストを提案できるようにすることで、入力を高速化する方法を探しています。

  1. 入力のすべての文字がキーワードに含まれていることが期待されます
  2. 入力内の文字は、キーワード内で同じ順序であることが期待されます
  3. 返されるキーワードのリストは、一貫した (再現可能な) 順序で提示する必要があります
  4. アルゴリズムは大文字と小文字を区別しない必要があります

分析:

最初の 2 つの要件は次のように要約できます。入力に対して、axgこの正規表現に一致する単語を探します。[^a]*a[^x]*x[^g]*g.*

3 番目の要件は、意図的に緩くしています。リストに表示される単語の順序は一貫している必要があります...ただし、スコアリングのアプローチがアルファベット順よりも優れているかどうかを推測するのは困難です。リストが非常に長い場合は、スコアリング アプローチの方が優れている可能性がありますが、リストが短い場合は、明確な方法で並べ替えられたリストから特定のアイテムを探す方が簡単です。

また、アルファベット順には、入力中の一貫性という利点があります。つまり、文字を追加してもリストが完全に並べ替えられるわけではなく (目と頭に負担がかかります)、もはや一致しない項目が除外されるだけです。

àUnicode文字の処理について正確性はありませんa。現在、そのような文字をキーワードに使用している言語を私は知らないので、ここでは省略します。

私の解決策：

どの入力に対しても、前に表現した正規表現を作成します。言語は既に大文字と小文字を区別しないマッチングを備えているため、Python に適しています。

次に、(アルファベット順に並べ替えられた) キーワードのリストを照合し、フィルター処理して出力します。

擬似コード:

WORDS = ['Bar', 'Foo', 'FooBar', 'Other']

def GetList(input, words = WORDS):
  expr = ['[^' + i + ']*' + i for i in input]
  return [w for w in words if re.match(expr, w, re.IGNORECASE)]

ワンライナーを使用することもできましたが、コードがわかりにくくなると思いました;)

ユーザーが文字を追加すると、計算した結果を単純に再フィルタリングできるため、このソリューションは増分的な状況 (つまり、ユーザー タイプとして一致し、再構築を続ける場合) に非常にうまく機能します。したがって：

  • 文字数が少ないため、マッチングが速く、リストの長さはあまり重要ではありません
  • たくさんの文字があり、これは短いリストをフィルタリングしていることを意味するため、マッチングに要素ごとに少し時間がかかってもあまり問題になりません

また、この正規表現にはバックトラッキングが含まれていないため、非常に効率的であることにも注意してください。また、単純なステート マシンとしてモデル化することもできます。

于 2010-05-24T12:52:35.660 に答える
9

レーベンシュタインの 'Edit Distance' アルゴリズムは、あなたがしようとしていることに対して間違いなく機能します: 2 つの単語、住所、電話番号、詩篇、モノローグ、学術論文がどれだけ一致しているかを測定し、結果と最適な一致を選択します。

より軽量なアプローチは、一般的な部分文字列を数えることです。レーベンシュタインほど良くはありませんが、使用可能な結果を​​提供し、高速な「InString」関数にアクセスできる遅い言語ですばやく実行できます。

数年前、Excellerando で Excel の「Fuzzy Lookup」を公開しました。「FuzzyMatchScore」関数を使用して、私が知る限り、まさに必要なものです。

http://excellerando.blogspot.com/2010/03/vlookup-with-fuzzy-matching-to-get.html

もちろん、Visual Basic for Applications にもあります。十字架とニンニクに注意して進みます。

Public Function SumOfCommonStrings( _
                            ByVal s1 As String, _
                            ByVal s2 As String, _
                            オプション VBA.VbCompareMethod = vbTextCompare, _ として比較
                            オプションの整数としての iScore = 0 _
                                ) 整数として

Application.Volatile False

' N.Heffernan 2006 年 6 月 6 日
' このコードはパブリック ドメインにあります


' 文字列 1 のどの部分が文字列 2 で見つかった部分文字列で構成されているかを測定する関数

' この関数は、変更された最長共通文字列アルゴリズムを使用します。
' 単純な LCS アルゴリズムは、1 文字に過度に敏感です
' テスト語の中点付近の削除/変更、例:
' 水曜日は明らかに編集距離で水曜日Xesday に近い
' 基本は WednesXXX です。だから得点したほうがいい
' '水曜日' と 'esday' を合計し、一致した合計を合計します

' 長さが異なる文字列に注意してください:
'
' SumOfCommonStrings("水曜日", "水曜日XXX日")
'
' これは次のスコアと同じです。
'
' SumOfCommonStrings("水曜日", "水曜日")
'
' そのため、呼び出し元の関数が最長の長さを使用していることを確認してください
' このスコアから類似度を計算する際の文字列。


' これは、パフォーマンスのためではなく、わかりやすくするためにコード化されています。

Dim arr() As Integer ' スコアリング マトリックス
Dim n As Integer ' s1 の長さ
Dim m As Integer ' s2 の長さ
Dim i As Integer ' s1 の開始位置
Dim j As Integer ' s2 の開始位置
Dim subs1 As String ' s1 の部分文字列
Dim len1 As Integer ' subs1 の長さ

Dim sBefore1 ' コードに記載
Dim sBefore2
Dim sAfter1
Dim sAfter2

文字列として薄暗いs3


SumOfCommonStrings = iScore

n = レン(s1)
m = レン(s2)

もし s1 = s2 なら
    SumOfCommonStrings = n
    終了機能
終了条件

n = 0 または m = 0 の場合
    終了機能
終了条件

's1 は、常に 2 つの文字列のうち短い方にする必要があります。
n > m の場合
    s3 = s2
    s2 = s1
    s1 = s3
    n = レン(s1)
    m = レン(s2)
終了条件

n = レン(s1)
m = レン(s2)

' 特殊なケース: s1 は s2 の正確な部分文字列です
If InStr(1, s2, s1, Compare) Then
    SumOfCommonStrings = n
    終了機能
終了条件

For len1 = n To 1 Step -1

    i = 1 の場合 n - len1 + 1 へ

        subs1 = Mid(s1, i, len1)
        j = 0
        j = InStr(1, s2, subs1, 比較)

        j > 0 の場合

            ' 一致する部分文字列が見つかりました...
            iScore = iScore + len1            

          ' s1 と s2 からこの部分文字列を切り取ります...
          ' そして、この切り出しの前後のフラグメントを検索します。


            i > 1 かつ j > 1 の場合
                sBefore1 = 左 (s1, i - 1)
                sBefore2 = 左 (s2, j - 1)
                iScore = SumOfCommonStrings(sBefore1, _
                                            sBefore2、_
                                            比較、 _
                                            iScore)
            終了条件


            i + len1 < n かつ j + len1 < m の場合
                sAfter1 = 右 (s1, n + 1 - i - len1)
                sAfter2 = 右 (s2, m + 1 - j - len1)
                iScore = SumOfCommonStrings(sAfter1, _
                                            sAfter2、_
                                            比較、 _
                                            iScore)
            終了条件


            SumOfCommonStrings = iScore
            終了機能

        終了条件

    次


次


終了機能


Private Function Minimum(ByVal a As Integer, _
                         ByVal b As Integer, _
                         ByVal c As Integer) As Integer
Dim min As Integer

  最小 = a

  b < min の場合
        最小 = b
  終了条件

  c < min の場合
        最小 = c
  終了条件

  最小 = 最小

終了機能
于 2011-01-11T17:26:45.260 に答える
3

私がこれまでに見つけた2つのアルゴリズム：

  1. LiquidMetal
  2. より良いIdoフレックスマッチング
于 2010-05-23T11:53:19.957 に答える
2

私は最近、同じ問題を解決しなければなりませんでした。私の解決策は、文字が連続して一致する文字列を高く評価し、入力された文字を順番に含まない文字列を除外することです。

ここでアルゴリズムの詳細を文書化しました: http://blog.kazade.co.uk/2014/10/a-fuzzy-filename-matching-algorithm.html

于 2014-10-31T08:20:20.367 に答える
0

テキストの大部分が英語である場合は、さまざまな Soundex アルゴリズムを試すことができます 1. Classic soundex 2. Metafone

これらのアルゴリズムを使用すると、互いに似ている単語を選択できるため、スペルミスのある単語を見つけるのに役立ちます。

于 2010-05-23T11:43:03.837 に答える