スペルチェック：2つの文字列の間に1対1のトークンの違いのマッピングを見つける

Question

最近インターネットのアーカイブでこの質問に遭遇しました。私は2つの文字列の間の異なるトークンの間に望ましいマッピングを見つけたいと思っています。出力には、StringからStringへのマップが必要です。例えば

：

文字列1：ヒューレット・パッカード企業

出力NYでアメリカの鉄道を助けた：hewlottpackardenterpriseは

文字列2がNYでアメリカのralewaysを助けた
hewlottpackardenterprise - >ヒューレット・パッカード企業

を

hewlott - > hewlett

raleways - >鉄道

NY - > NY

注：私は削除などの種類によって分離編集のすべての種類を（、見つかった編集距離法を、書くことができました置換など）、最初の文字列をconvertメソッドで変換することができます

これまで何を試みましたか？

アプローチ1：私はハッシュマップに最初の文字列のトークンを挿入し、このハッシュマップと他の文字列のトークンを比較し、スペースで文字列の両方を分割する単純なアプローチで始まりました。しかし、このアプローチは、関連するマッピングのミスとしてすぐには失敗します。

アプローチ2：私はcovertメソッドを使用して、文字列の編集位置と編集のタイプを検索します。スペースの編集を使用して、hewlottpackardenterprise - > hewlett packardenterpriseからマッピングを作成できます。しかし、この方法は、同じ単語の中でより多くのものを分割する必要があるほど、爆発的なものになります。

この点についてご意見をお寄せください。コメントの疑いが解消されます。

は

public String returnWhiteSpaceEdittoken(EditDone e, List<String> testTokens) { 
    int pos = e.pos, count=0, i=0; 
    String resultToken = null; 

    if (e.type.equals(DeleteEdit)) { 
     for (i=0;i<testTokens.size();i++) { 
      count+=testTokens.get(i).length(); 
      if (count==pos) { 
       break; 
      } 
      if (i!=testTokens.size()-1) { 
       count++; 
      } 
     } 

     resultToken = testTokens.get(i) + " " + testTokens.get(i+1); 
    } else if (e.type.equals(InsertEdit)) { 
     for (i=0;i<testTokens.size();i++) { 
      count+=testTokens.get(i).length(); 
      if (count>pos) { 
       break; 
      } 
      if (i!=testTokens.size()-1) { 
       count++; 
      } 
     } 
     String token = testTokens.get(i); 
     resultToken = token.substring(count-token.length(), pos) + token.substring(pos, count); 
    } 
    return resultToken; 
} 

Answer 1

このような問題を処理するのはかなり一般的な方法は、最長共通部分列を見つけることである（またはそれが最短編集スクリプトデュアルだ）、2つの文字列とポストプロセスの間、必要な特定のフォーマットを取得するための出力;あなたの場合は文字列マップ。

ウィキペディアは、ここで問題にかなりまともな紹介があります。https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

と大きな紙マイヤーズによる「O（ND）の違いアルゴリズムとそのバリエーションは、」ここで見つけることができます。 http://www.xmailserver.org/diff2.pdf