文字列セット内の一般的な文字を判別するために使用できるアルゴリズムは何ですか?
例を簡単にするために、2 つ以上の文字が連続して表示され、それがサンプルの 2 つ以上に表示されるかどうかだけを気にします。例えば：
知りたい:
00 は 1,2,3,4
で使用 000 は1,2,3,4
で使用 0000 は 1,2,3
で使用 00000 は 2,3
ab で使用 1,2,3,4
abcで使用1,2,3,4 で使用されました
abcd は 1,2で使用されまし
た bcd は
1,2,3,4 で使用されましたbcd は 1,2
で使用されました cd は 1,2 で使用されました
de は 1,4 で使用されました
これは宿題ではないと思います。（もしそうなら、あなたはあなた自身の盗作です！;-)
以下は、手っ取り早い解決策です。時間計算量は次のとおりですO(m**2 * n)。ここmで、は平均文字列長であり、nは文字列配列のサイズです。
のインスタンスはOccurrence、指定された文字列を含むインデックスのセットを保持します。commonOccurrencesルーチンは文字列配列をスキャンし、null以外の各文字列を呼び出しますcaptureOccurrences。captureOccurrencesルーチンは、現在のインデックスを、指定されOccurrenceた文字列の可能なサブ文字列ごとに配置します。最後に、少なくとも2つのインデックスを持つcommonOccurrencesものだけを選択して、結果セットを作成します。Occurrences
サンプルデータには、質問で特定したよりも多くの一般的なサブストリングが含まれていることに注意してください。たとえば"00ab"、各入力文字列で発生します。コンテンツ（たとえば、すべての数字、すべてのアルファベットなど）に基づいて興味深い文字列を選択するための追加のフィルターは、読者の練習問題として残されています。;-)
迅速で汚いJavaソース：
package com.stackoverflow.answers;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;
public class CommonSubstringFinder {
public static final int MINIMUM_SUBSTRING_LENGTH = 2;
public static class Occurrence implements Comparable<Occurrence> {
private final String value;
private final Set<Integer> indices;
public Occurrence(String value) {
this.value = value == null ? "" : value;
indices = new TreeSet<Integer>();
}
public String getValue() {
return value;
}
public Set<Integer> getIndices() {
return Collections.unmodifiableSet(indices);
}
public void occur(int index) {
indices.add(index);
}
public String toString() {
StringBuilder result = new StringBuilder();
result.append('"').append(value).append('"');
String separator = ": ";
for (Integer i : indices) {
result.append(separator).append(i);
separator = ",";
}
return result.toString();
}
public int compareTo(Occurrence that) {
return this.value.compareTo(that.value);
}
}
public static Set<Occurrence> commonOccurrences(String[] strings) {
Map<String,Occurrence> work = new HashMap<String,Occurrence>();
if (strings != null) {
int index = 0;
for (String string : strings) {
if (string != null) {
captureOccurrences(index, work, string);
}
++index;
}
}
Set<Occurrence> result = new TreeSet<Occurrence>();
for (Occurrence occurrence : work.values()) {
if (occurrence.indices.size() > 1) {
result.add(occurrence);
}
}
return result;
}
private static void captureOccurrences(int index, Map<String,Occurrence> work, String string) {
final int maxLength = string.length();
for (int i = 0; i < maxLength; ++i) {
for (int j = i + MINIMUM_SUBSTRING_LENGTH; j < maxLength; ++j) {
String partial = string.substring(i, j);
Occurrence current = work.get(partial);
if (current == null) {
current = new Occurrence(partial);
work.put(partial, current);
}
current.occur(index);
}
}
}
private static final String[] TEST_DATA = {
"0000abcde0000",
"0000abcd00000",
"000abc0000000",
"00abc000de000",
};
public static void main(String[] args) {
Set<Occurrence> found = commonOccurrences(TEST_DATA);
for (Occurrence occurrence : found) {
System.out.println(occurrence);
}
}
}
サンプル出力:(実際には1行に1回しか発生しなかったことに注意してください。ブロッククォートのマークアップが行をマージするのを防ぐことはできないようです）
"00"：0,1,2,3 "000"：0,1,2,3
"0000"：0,1,2 "0000a"：0,1
"0000ab"：0,1 "0000abc"：0 、1
"0000abcd"：0,1 "000a"：0,1,2
"000ab"：0,1,2 "000abc"：0,1,2
"000abcd"：0,1 "00a"：0,1 、2,3
"00ab"：0,1,2,3 "00abc"：0,1,2,3
"00abc0"：2,3 "00abc00"：2,3
"00abc000"：2,3 "00abcd" ：0,1
"0a"：0,1,2,3 "0ab"：0,1,2,3
"0abc"：0,1,2,3 "0abc0"：2,3
"0abc00"：2 3 "0abc000"：2,3
"0abcd"：0,1 "ab"：0,1,2,3 "abc"：0,1,2、3 "abc0"：2,3 "abc00"：2,3
"abc000"：2,3 "abcd"：0,1 "bc"：0,1,2,3 "bc0"：2,3 "bc00" ：2,3
"bc000"：2,3 "bcd"：0,1 "c0"：2,3 "c00"：2,3 "c000"：2,3 "cd"：0,1
"de"：0,3 "de0"：0,3 "de00"：0,3
"e0"：0,3 "e00"：0,3
これはおそらく NP 困難な問題です。これは、複数の配列アラインメントに似ています。基本的に、ニーズに合わせて多次元の Smith-Waterman (= ローカル シーケンス アラインメント) を適用できます。ただし、より効率的なアルゴリズムがあるかもしれません。
ツリーを通るパスが文字シーケンスであるツリーを構築します。各ノードに、文字列参照が追加される「セット」が含まれているようにします (または単にカウントを保持します)。次に、N が関心のある最長のシーケンスである単語内の N 個の位置を追跡します (たとえば、各文字で新しいハンドルを開始し、各ステップですべてのハンドルを下に移動し、N ステップ後に各ハンドルを中止します)。
これは、小さく、有限で、密度の高いアルファベットでうまく機能します (DNA は、私がそれを使用すると考えた最初の場所でした)。
編集:気になるパターンが事前にわかっている場合は、事前にツリーを構築し、ツリーを拡張するのではなく、ツリー上にいるかどうかのみを確認することで、上記を変更して機能させることができます。
例
入力
abc
abd
abde
acc
bde
木
a : 4
b : 3
c : 1
d : 2
e : 1
c : 1
c : 1
b : 4
d : 3
e : 2
c : 1
c : 3
c : 1
d : 3
e : 2
Webで「サフィックスツリー」を検索します。または、Dan Gusfieldによる「文字列、ツリー、シーケンスのアルゴリズム」を入手してください。確認する本はありませんが、接尾辞木のウィキペディアのページには、205ページに「セット内の少なくともk個の文字列に共通する最長の部分文字列を見つける」という問題の解決策が含まれていると書かれています。
事前に検索する必要がある「値」を知っていますか? または、文字列を解析して、投稿したような統計を表示するコードが必要ですか?
Boyer-Moore アルゴリズムを使用すると、探しているものが事前にわかっている場合、部分文字列が存在するかどうか (およびその場所を特定することさえ) を非常に迅速に判断できます。
距離行列の分析を使用できます。斜めの移動 (コストの変更なし) は完全に一致します。
共通部分文字列がデータ内にどれだけ頻繁に含まれるかによっては、接尾辞配列が接尾辞ツリーよりも単純で効率的であることに気付くかもしれません。それらが十分に共通している場合は、より洗練された接尾辞配列構築アルゴリズムが必要になります。(単純な方法は、ライブラリの並べ替え関数を使用することです。)