ユニークな部分文字列に基づくペア文字列

Question

可能な場合は、各ペアの同じ部分文字列（下の例では太字のテキスト、強調するために太字/大文字のみを使用しています）に一致する2組の文字列がありますそれぞれのリスト内でユニークなリスト要素を調べることによってキー部分文字列を特定する）。テキストの残りの部分（lorem ipsum）は、多くの要素に共通する場合もあれば、完全に一意である場合もあります。

リスト1：

1. "Loremのイプサム嘆き座るAMET、CANDY BAR consecteturのadipisicing ELIT、"
2. "SEDはincididunt UT tempor eiusmod CANDYのCANEを行うlaboreらdolore マグナ"
3. "eedod eiusmod tempor HOMER incididunt ut labo et dolore magna"
4. "Loremのイプサム嘆き、AMET consecteturのadipisicing PICKUP TRUCK ELIT座る"
5. 「ullamcoのlaborisのNiSi UT aliquipの元のEA commodoのconsequat。 Duisのaute "

リスト2：

1. は、 "SEDはeiusmod"
2. " laboreらdoloreマグナaliquaをincididunt HOMER UTをtemporありません。 キャンディーバー quis nostrud exercitation "
3. " aliqua。ユタenim広告ミニムveniam、nostrud CANDYのCANEをQUIS exercitation」
4. "irure悲しみでreprehenderitでvoluptate velit ESSE cillum dolore"
5. "Loremのイプサム悲しみは
"、AMET consecteturのadipisicing ピックアップトラック ELIT座ります試合以下のサンプルテキストから

です：1-2; 2-3; 3-1; 4-5

リスト1の要素5とリスト2の要素4何も一致しない

。

Answer 1

扱うデータの総量が比較的少ない場合は、すでに提案されているソリューション（.contains()または正規表現を使用）がおそらく最も実用的です。 以下は、データ量がはるかに多い場合に行う方法です。

解決策の重要な部分は、接尾辞配列を使用することです。サフィックス配列は、テキスト（または複数のテキストの連結）のすべてのサフィックス（文字列の意味で、言語的サフィックスではありません）の辞書順ソートされたリストです。

説明した例では、という2つのセットのうちの1つのの連結テキストの接尾辞配列を作成する必要があります。独自の区切り文字を使用して、私たちはセット2のためにこれを行うと仮定しますので、我々はすべての文章を連結でしょう（私はハッシュ文字以下#選択している）：

sed do eiusmod tempor incididunt HOMER ut labore et dolore magna#aliqua. Ut enim ad minim veniam, CANDY BAR quis nostrud exercitation#aliqua. Ut enim ad minim veniam, quis nostrud CANDY CANE exercitation#.... 

次に、あなたが構築したいです接尾辞配列の文字列と、最長共通接頭辞配列（LCP）。両方のデータ構造は、テキストの量が極端に大きくない場合はブルートフォースアプローチを使用して構築できます。あるいは、それらをより効率的に構築するためのライブラリ、たとえばjSuffixArraysがあります。

最後にあなたがの文章を反復処理は、1を設定し、それぞれの文の候補者を通じて、関連するトークン（空白または句読点をたどるおそらく唯一の単語）の位置を開始し、それらのためのセット2の接尾辞配列を検索します。 LCP配列が使用可能なときに接尾辞配列を検索すると、O（n + m）時間で実行できます（nはセット2の連結文字列の長さ、mは探している候補文字列の長さです）。 classical search algorithm by Manber and Myersですが、まだ遅すぎる場合は、洗練された方法があります。 Navarro and Mäkinen 2007に記載されている。

接尾辞配列には、文字列がセット2でどのくらい頻繁に出現するか、そしていくつの異なる文章であるかに関する情報が簡単に提供されます。私は必要に応じてこの投稿への編集で後者をどうやって行うのかを詳しく説明することができます。

Answer 2

私はあなたが各リスト内でユニークな文字列のリストを持っていることを理解しています。これらの文字列は、リスト内の文字列の一部（部分文字列）です。私はそのような部分文字列のリストを作成し、正規表現を使ってそれらを比較します（この場合、Javaの部分文字列はなく、開始インデックスを知る必要があります）。