47

たとえば、一連の文字列が与えられた場合:

EFgreen
EFgrey
EntireS1
EntireS2
J27RedP1
J27GreenP1
J27RedP2
J27GreenP2
JournalP1Black
JournalP1Blue
JournalP1Green
JournalP1Red
JournalP2Black
JournalP2Blue
JournalP2Green

これらが 3 つのファイル セットであることを検出できるようにしたいと考えています。

  • 全体[1,2]
  • J27[赤、緑]P[1,2]
  • JournalP[1,2][赤、緑、青]

この問題にアプローチする既知の方法はありますか?これについて読むことができる公開された論文はありますか?

私が検討しているアプローチは、文字列ごとに他のすべての文字列を見て、共通の文字と異なる文字がどこにあるかを見つけ、最も共通している文字列のセットを見つけようとすることですが、これはあまり効率的ではなく、偽陽性。

これは、 「ファイル名に含まれる一般的な文字列のグループを検出する方法」と同じではないことに注意してください。これは、文字列には常に一連の数字が続くことを前提としているためです。

4

9 に答える 9

12

ここから始めます: http://en.wikipedia.org/wiki/Longest_common_substring_problem

外部リンクには、記事で説明されている 2 つのアルゴリズムの Perl 実装を含む補足情報へのリンクがあります。

追加するために編集：

議論に基づいて、Longest Common Substring がこの問題の中心にある可能性があると考えています。コメントで参照している Journal の例でも、そのセットの特徴を定義するのは部分文字列「Journal」です。

最初に、セットを他のセットとは別に定義するものを検討します。これにより、データを分割するためのパーティションが得られます。問題は、セット内にどれだけの共通性が存在するかを測定することです。定義特性が共通部分文字列である場合、Longest Common Substring が論理的な開始点になります。

セット検出のプロセスを自動化するには、一般に、可能なすべてのペア間の「差」を測定するために使用できる共通性のペアごとの測定が必要です。次に、合計差が全体的に最小になる分割を計算するアルゴリズムが必要です。差分測定値が最長共通部分文字列でない場合は問題ありませんが、それが何になるかを判断する必要があります。明らかに、それは測定できる具体的なものである必要があります。

また、差分測定のプロパティは、パーティションの作成に使用できるアルゴリズムに影響することにも注意してください。たとえば、diff(X,Y) が X と Y の差の測定値を与えると仮定します。距離の測定値が diff(A,C) <= diff(A,B) + diff のようなものである場合、おそらく有用です。 （紀元前）。そして明らかに diff(A,C) は diff(C,A) と同じでなければなりません。

これについて考えると、「差」を任意の 2 つの文字列間の距離と見なすことができるかどうか、距離の厳密な定義を使用して、入力文字列に対して何らかのクラスター分析を試みることができるかどうかも疑問に思い始めます。 . ちょっとした考え。

于 2009-09-11T13:26:01.623 に答える
3

そのようなものがうまくいくかもしれません。

  1. すべての文字列を表すトライを作成します。

あなたが与えた例では、ルートから「E」と「J」の2つのエッジがあります。その後、「J」ブランチは「Jo」と「J2」に分割されます。

  1. EntireS-(forks to 1, 2) のように分岐する単一のストランドは、選択を示すため、EntireS[1,2] になります。

  2. 分岐に関連してストランドが「短すぎる」場合、たとえば BA-(NANA と HAMAS への分岐) の場合、選択肢 ("ba[nana,hamas]") ではなく 2 つの単語 ("banana, bahamas") をリストします。 . 「短すぎる」は、「フォークの後の部分が前の部分よりも長い場合」のように単純な場合もあれば、特定の接頭辞を持つ単語の数によって重み付けされる場合もあります。

  3. 2 つのサブツリーが「十分に類似」している場合、それらをマージして、ツリーの代わりに一般的なグラフを作成できます。たとえば、ABRed、ABBlue、ABGreen、CDRed、CDBlue、CDGreen がある場合、「AB」をルートとするサブツリーが「CD」をルートとするサブツリーと同じであることがわかる場合があるため、それらをマージします。あなたの出力では、これは次のようになります: [左枝、右枝][サブツリー]、したがって: [AB,CD][赤、青、緑]. 近いがまったく同じではないサブツリーを処理する方法は? おそらく絶対的な答えはありませんが、ここにいる誰かが良い考えを持っているかもしれません.

この回答コミュニティ wiki をマークしています。一緒に、質問に対する合理的な回答を得ることができるように、お気軽に延長してください.

于 2009-09-11T14:21:30.477 に答える
2

文字列の類似性には多くのアプローチがあります。レーベンシュタイン距離などの多くのメトリックを実装するこのオープンソース ライブラリを確認することをお勧めします。

http://sourceforge.net/projects/simmetrics/

于 2009-09-11T14:15:06.610 に答える
2

「frak」を試してください。文字列のセットから正規表現を作成します。多分それのいくつかの変更があなたを助けるでしょう。 https://github.com/noprompt/frak

それが役に立てば幸い。

于 2013-11-12T03:51:15.987 に答える
1

これは、一般化されたサフィックス ツリーで実現できるはずです。サフィックス ツリーで、複数のソース文字列からの長いパスを探します。

于 2012-05-02T22:14:21.997 に答える
0

この特定の文字列の例では、単純な単語/数字の区切りを使用することを考慮して、非常に単純にします。

数字以外のシーケンスは、大文字 (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]

次に、グループごとにグループ化を開始すると、プレフィックス「Entire」がいくつかのグループに共通であり、すべてのサブグループがヘッドグループとして S を持っているため、それらの変数のみが 1,2 であることがすぐにわかります。J27 の場合、J27 は葉のみですが、赤と緑で分岐していることがわかります。

したがって、ある種の List<Pair<list, string>> -structure (正しく思い出せば複合パターン)。

于 2009-09-11T14:30:44.687 に答える
0 
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));
    }
}
于 2013-10-25T06:16:14.620 に答える