34

最も類似した文字列のリストをフィルタリングするために、2つの文字列を比較し、それらの類似性を計算する必要があります。

例えば。「犬」を検索すると

  1. 犬
  2. doggone
  3. ボグ
  4. 霧
  5. 霧

例えば。「クラック」を検索すると、

  1. 割れ目
  2. 賢明な亀裂
  3. ラック
  4. ジャック
  5. いんちき

私は出くわしました：

これ以上の文字列類似性アルゴリズムを知っていますか？

4

5 に答える 5

31

レーベンシュタイン距離は私がお勧めするアルゴリズムです。1つの文字列を別の文字列に変更するために実行する必要のある操作の最小数を計算します。変更が少ないということは、文字列がより類似していることを意味します...

于 2010-08-26T14:47:37.357 に答える
20

ある種のあいまい一致が必要なようです。これは、類似性メトリックのセットのJava実装ですhttp://www.dcs.shef.ac.uk/~sam/stringmetrics.html。文字列メトリックの詳細については、http： //www.cs.cmu.edu/~wcohen/postscript/ijcai-ws-2003.pdfを参照してください。これは、実装のあいまいさや実装の速度によって異なります。

于 2010-08-26T15:24:28.710 に答える
9

trieパフォーマンスに重点を置いている場合は、構造に基づいたアルゴリズムを実装します
（テキスト内の単語を検索したり、単語を修正したりするのに役立ちますが、あなたの場合、特定の単語を含むすべての単語またはすべてをすばやく見つけることができますたとえば、1文字）。

最初に上記のウィキペディアのリンクをたどってください。Triesは最速の単語ソート方法です（nワード、検索s、O（n）でトライを作成し、O（1）で検索します（または、必要に応じて、aが平均の長さである場合、トライのO（an ）とO（s）for the search））。

問題（類似した単語）の（最適化される）迅速で簡単な実装は、

  • 単語のリストを使用してトライを作成し、すべての文字を前後にインデックス付けします（以下の例を参照）
  • sを検索するには、 s [0]から繰り返してトライ内の単語を検索し、次にs [1]など...
  • トライでは、見つかった文字の数がlen（s）-kの場合、単語が表示されます。ここで、kは許容値です（1文字が欠落している、2 ...）。
  • アルゴリズムは、リスト内の単語に拡張できます（以下を参照）

例、単語car、vars。

トライを構築します（大きな文字はここで単語が終わることを意味しますが、別の単語は続く場合があります）。は>ポストインデックス（進む）であり、<プレインデックス（戻る）です。別の例では、開始文字も示す必要がある場合がありますが、わかりやすくするためにここでは示していません。たとえば、C ++ではとはになります。
つまり、から、に直接移動でき、逆にからに移動することもできます。<>Mystruct *previous,*nexta > c < racaR

  1.  c < a < R
  2.  a > c < R
  3.    > v < r < S
  4.  R > a > c
  5.        > v < S
  6.  v < a < r < S
  7.  S > r > a > v

厳密に車を探すと、トライで1からアクセスできます。車が見つかります（車で始まるものはすべて見つかりますが、車が中にあるものもすべて見つかります。例にはありませんが、たとえば牧師が見つかります。からc > i > v < a < R）。

1文字の間違った/欠落した許容範囲を許可しながら検索するには、sの各文字から繰り返し、連続した数を数えます-または1文字をスキップして-トライのsから取得した文字。

探してcar、

  • cc < a：トライでandを検索します（ sのc < r文字がありません）。単語wで間違った文字を受け入れるには、各反復で間違った文字をジャンプして、遅れているかどうかを確認します。これはO（w）です。O（w²）などの2つの文字を使用しますが、文字のジャンプを考慮して、別のレベルのインデックスをトライに追加することもできます。これにより、トライが複雑になり、メモリに関して貪欲になります。ar
  • a、次にr：上記と同じですが、逆方向にも検索します

これは、原則についてのアイデアを提供するためだけのものです。上記の例には、いくつかの不具合がある可能性があります（明日もう一度確認します）。

于 2010-08-26T17:00:19.553 に答える
1

あなたはこれを行うことができます：

 干し草の山のForeach文字列 オフセットを実行：= -1;
    matchCharacters：= 0;
    針のForeach文字オフセットを実行：= PositionInString（string 、 char 、offset +1）;
        オフセット=-1の場合、ブレーク;
        終了;
        一致した文字：=一致した文字+ 1;
    終了;
    一致した場合Characters > 0Then  
        
         
             
       //（部分的な）一致が見つかりました
    終了;
終了;

matchCharactersを使用すると、一致の「程度」を判別できます。針の長さと等しい場合、針のすべての文字も文字列になります。最初に一致した文字のオフセットも保存する場合は、最後に一致した文字のオフセットのオフセットから最初に一致した文字のオフセットを引くことにより、一致した文字の「密度」で結果を並べ替えることもできます。差が小さいほど、一致の密度が高くなります。

于 2010-08-26T14:59:19.967 に答える
0 
class Program { 
    static int ComputeLevenshteinDistance(string source, string target) {
        if ((source == null) || (target == null)) return 0;
        if ((source.Length == 0) || (target.Length == 0)) return 0;
        if (source == target) return source.Length;

        int sourceWordCount = source.Length;
        int targetWordCount = target.Length;

        int[,] distance = new int[sourceWordCount + 1, targetWordCount + 1];

        // Step 2
        for (int i = 0; i <= sourceWordCount; distance[i, 0] = i++);
        for (int j = 0; j <= targetWordCount; distance[0, j] = j++);

        for (int i = 1; i <= sourceWordCount; i++) {
            for (int j = 1; j <= targetWordCount; j++) {
                // Step 3
                int cost = (target[j - 1] == source[i - 1]) ? 0 : 1;

                // Step 4
                distance[i, j] = Math.Min(Math.Min(distance[i - 1, j] + 1, distance[i, j - 1] + 1), distance[i - 1, j - 1] + cost);
            }
        }

        return distance[sourceWordCount, targetWordCount]; 
    }

    static void Main(string[] args){ 
       Console.WriteLine(ComputeLevenshteinDistance ("Stackoverflow","StuckOverflow"));
       Console.ReadKey();
    }
}
于 2017-07-24T21:16:18.313 に答える