テキストを解析して類似点を返す

Question

私はいくつかのURLを持っていて、それぞれのURLからbasenameを返すとします。

http://www.test.com/the.code.r00 

は

the.code.r00 

を返しますし、私は私が他のURLからあまりにも以下のベース名を持っているものと

the.code.r00 
the.code.r01 
.. 
... 
the.code.r12 

と一緒に動作するように、いくつかのURLから抽出された複数のベース名を持つ

the.matrix.r00 
the.matrix.r01 
.. 
... 
the.matrix.r14 

私がテストし、私は上記のベース名を解析した後

the.code.r 
the.matrix.r 

を返すことが証明された知られているアルゴリズムがありますかどうかを知りたいのです。

また、代わりに、スーパーであるのと同じことをするいくつかの* nixツールがあります。

フォーマットは常に上記のようなものではないことに注意してください。そうでなければ、単純なsubstrを実行できました。数字は、文字列の特定の場所に常にリストされているとは限りません。その他の例

the.code.part01.rar 
the.code.001 
.. 
.... 

..私はこれを行うには、私自身のアルゴリズムを実装することができますが、私はすでに定義されたものがある場合は、既知のアルゴリズムを使用することを好むと思いますので、それはおそらく、いくつかの重いテストを行わずにバグの缶だろう

Answer 1

longest common substring problemのアンカー実装を探している可能性があります。文字列のリストをソートし、隣接する要素にアンカーLCSを実行します。 LCSをキーとして、2つの文字列を値として、複数値のハッシュマップにLCSを挿入します。

これを済ませたら、あるしきい値を満たすまで、LCS文字列と同じ操作を行います。

Answer 2

リスト内の各文字列のペアを調べて、Levenshtein Distance（別名文字列編集距離）を計算します。これにより、一方の文字列を他方の文字列に変更するのに必要な変更の最小回数が得られます。

これで、Levenshteinの実装から、文字列間の実際の変更セットを得ることができます（動的プログラムのバックポインタに従うことによって）。変更のセットが他の数字に代わる数字だけで構成されている場合は、パターンが見つかりました。文字列の1つをコピーし、それらの数字を削除し、パターンセットに格納して、他の文字列ペアを続行します。