文字列のリストで一般的な部分文字列を検出するにはどうすればよいですか
https://stackoverflow.com/questions/1410822
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
一連の文字列を指定します。例：
EFgreen
EFgrey
EntireS1
EntireS2
J27RedP1
J27GreenP1
J27RedP2
J27GreenP2
JournalP1Black
JournalP1Blue
JournalP1Green
JournalP1Red
JournalP2Black
JournalP2Blue
JournalP2Green
これらが3つのファイルセットであることを検出できるようにしたい：
- EntireS [1,2]
- J27 [赤、緑] P [1,2]
- JournalP [1,2] [赤、緑、青]
この問題に対処するための既知の方法はありますか？これについて読むことができる公開された論文はありますか？
私が検討しているアプローチは、各文字列が他のすべての文字列を見て、共通の文字と異なる文字がある場所を見つけ、最も共通する文字列のセットを見つけようとしていますが、これはあまり効率的ではないことを恐れています誤検知を引き起こす可能性があります。
これは 'と同じではないことに注意してくださいファイル名に含まれる一般的な文字列のグループを検出するにはどうすればよいですか、文字列には常に一連の数字が続くことを前提としています。
解決
ここから始めます： http://en.wikipedia.org/wiki/Longest_common_substring_problem
外部リンクには、記事で説明されている2つのアルゴリズムのPerl実装を含む補足情報へのリンクがあります。
追加して編集：
議論に基づいて、Longest Common Substringがこの問題の中心にある可能性がまだあると思います。コメントで参照するJournalの例でも、そのセットの定義特性はサブストリング「Journal」です。
最初に、セットを他のセットとは別のものとして定義するものを検討します。これにより、データを分割するパーティションが得られますが、問題はセット内にどれだけの共通性があるかを測定することです。定義特性が共通部分文字列である場合、最長共通部分文字列が論理的な開始点になります。
集合検出のプロセスを自動化するには、一般に、可能なすべてのペア間の「差異」を測定するために使用できる共通性のペアごとの測定が必要になります。次に、全体の合計差が最小になるパーティションを計算するアルゴリズムが必要です。差分測定値が最長共通部分文字列ではない場合は問題ありませんが、それが何であるかを判断する必要があります。明らかに、測定できる具体的なものである必要があります。
差分測定のプロパティは、パーティションの作成に使用できるアルゴリズムにも影響することに注意してください。たとえば、diff（X、Y）がXとYの差の測定値を与えると仮定します。距離の測定値がdiff（A、C）<！> lt; = diff（A、 B）+ diff（B、C）。そして明らかにdiff（A、C）はdiff（C、A）と同じでなければなりません。
これについて考えると、「差」を任意の2つの弦の間の距離と考えることができるかどうかも疑問に思うようになり、厳密な距離の定義により、ある種の入力文字列のクラスター分析。ただの考え。
他のヒント
すばらしい質問です！ソリューションへのステップは次のとおりです。
- トークン化入力
- トークンを使用して適切なデータ構造を構築します。 DAWG は理想的ですが、 Trie はよりシンプルで適切な出発点です。
- サブツリーを個別の出力に単純化またはクラスタリングするためのデータ構造のオプションの後処理
-
regroup.py でこのアプローチを実装しました。次に例を示します。
$ cat | ./regroup.py --cluster-prefix-len=2
EFgreen
EFgrey
EntireS1
EntireS2
J27RedP1
J27GreenP1
J27RedP2
J27GreenP2
JournalP1Black
JournalP1Blue
JournalP1Green
JournalP1Red
JournalP2Black
JournalP2Blue
JournalP2Green
^D
EFgre(en|y)
EntireS[12]
J27(Green|Red)P[12]
JournalP[12](Bl(ack|ue)|(Green|Red))
そのような何かが動作する可能性があります。
- すべての文字列を表すトライを構築します。
指定した例では、ルートから2つのエッジがあります。<！> quot; E <！> quot;および<！> quot; J <！> quot;。 <！> quot; J <！> quot;ブランチは<！> quot; Jo <！> quot;に分割されます。および<！> quot; J2 <！> quot;。
-
分岐する単一のストランド。 E-n-t-i-r-e-S-（1、2への分岐）は選択肢を示すため、EntireS [1,2]
-
ストランドが<！> quot;短すぎる<！> quot;フォークに関連して、例えばBA-（NANAとHAMASに分岐）、選択肢（<！> quot; ba [nana、hamas] <！> quot;ではなく、2つの単語（<！> quot; banana、bahamas <！> quot;）をリストします。 ）。 <！> quot;短すぎる<！> quot;フォークの後の部分が<！> quotの前の部分よりも長い場合は<！> quot;のように単純な場合もあれば、特定のプレフィックスを持つ単語の数で重み付けされる場合もあります。
-
2つのサブツリーが<！> quot;十分に類似している場合<！> quot;その後、それらをマージして、ツリーではなく一般的なグラフを作成できます。たとえば、ABRed、ABBlue、ABGreen、CDRed、CDBlue、CDGreenがある場合、サブツリーは<！> quot; AB <！> quotをルートにしていることがわかります。 <！> quot; CD <！> quot;をルートとするサブツリーと同じなので、それらをマージします。出力では、これは次のようになります。[左ブランチ、右ブランチ] [サブツリー]、つまり：[AB、CD] [赤、青、緑]。近いが完全に同じではないサブツリーを処理する方法は？おそらく絶対的な答えはありませんが、ここの誰かが良い考えを持っているかもしれません。
この回答コミュニティwikiをマークしています。遠慮なく拡張して、質問に対して適切な回答が得られるようにしてください。
文字列の類似性には多くのアプローチがあります。レーベンシュタイン距離のような多くのメトリックを実装するこのオープンソースのライブラリをご覧になることをお勧めします。
一般化されたサフィックスツリーでこれを達成できるはずです。サフィックスツリーで複数のソース文字列からの長いパスを探します。
try <！> quot; frak <！> quot; 。文字列のセットから正規表現を作成します。たぶんそれのいくつかの修正はあなたを助けるでしょう。 https://github.com/noprompt/frak
お役に立てば幸いです。
一般的な部分文字列を見つける一般的なケースを解決する多くの解決策が提案されています。ただし、ここでの問題はより専門的なものです。部分文字列だけでなく、一般的なプレフィックスを探しています。これにより、少し簡単になります。 最も長い共通プレフィックスを見つけるための良い説明は、 http://www.geeksforgeeks.org / longest-common-prefix-set-1-word-by-word-matching /
だから私の提案した<！> quot; pythonese <！> quot;擬似コードは次のようなものです（find_lcp：
def count_groups(items):
sorted_list = sorted(items)
prefix = sorted_list[0]
ctr = 0
groups = {}
saved_common_prefix = ""
for i in range(1, sorted_list):
common_prefix = find_lcp(prefix, sorted_list[i])
if len(common_prefix) > 0: #we are still in the same group of items
ctr += 1
saved_common_prefix = common_prefix
prefix = common_prefix
else: # we must have switched to a new group
groups[saved_common_prefix] = ctr
ctr = 0
saved_common_prefix = ""
prefix = sorted_list[i]
return groups
文字列のこの特定の例では、非常にシンプルに保つために、単純な単語/数字の区切りを使用することを検討してください。
数字以外のシーケンスは、明らかに大文字（Entire）で開始できます。すべての文字列をシーケンスのグループに分割した後、次のようになります
[Entire][S][1]
[Entire][S][2]
[J][27][Red][P][1]
[J][27][Green][P][1]
[J][27][Red][P][2]
....
[Journal][P][1][Blue]
[Journal][P][1][Green]
グループによるグループ化を開始すると、すぐにそのプレフィックス<！> quot; Entire <！> quot;が表示されます。一部のグループでは一般的であり、すべてのサブグループのヘッドグループとしてSがあるため、それらの変数のみが1,2です。 J27の場合、J27はリーフだけですが、その後赤と緑で分岐することがわかります。
したがって、リスト<！> lt;ペア<！> lt;リスト、文字列<！> gt; <！> gt; -structure（正しくリコールする場合は複合パターン）。
import java.util.*;
class StringProblem
{
public List<String> subString(String name)
{
List<String> list=new ArrayList<String>();
for(int i=0;i<=name.length();i++)
{
for(int j=i+1;j<=name.length();j++)
{
String s=name.substring(i,j);
list.add(s);
}
}
return list;
}
public String commonString(List<String> list1,List<String> list2,List<String> list3)
{
list2.retainAll(list1);
list3.retainAll(list2);
Iterator it=list3.iterator();
String s="";
int length=0;
System.out.println(list3); // 1 1 2 3 1 2 1
while(it.hasNext())
{
if((s=it.next().toString()).length()>length)
{
length=s.length();
}
}
return s;
}
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
System.out.println("Enter the String1:");
String name1=sc.nextLine();
System.out.println("Enter the String2:");
String name2=sc.nextLine();
System.out.println("Enter the String3:");
String name3=sc.nextLine();
// String name1="salman";
// String name2="manmohan";
// String name3="rahman";
StringProblem sp=new StringProblem();
List<String> list1=new ArrayList<String>();
list1=sp.subString(name1);
List<String> list2=new ArrayList<String>();
list2=sp.subString(name2);
List<String> list3=new ArrayList<String>();
list3=sp.subString(name3);
sp.commonString(list1,list2,list3);
System.out.println(" "+sp.commonString(list1,list2,list3));
}
}
