用於將一組字符串劃分爲大小相同的最小集合的算法

Question

我有一大組字符串。我想將字符串劃分爲以下子集：

1. 子集中的每個項目共享一個或多個連續字符。
2. 定義子集的共享連續字符對於該組子集是唯一的（即，共享字符足以定義與其他子集處於互斥關係的字符串子集）。
3. 子集的大小大致相同。
4. 生成的子集集合是符合上述條件所需的最小子集數。

例如給下面的一組名字：

艾倫，拉里，阿爾弗雷德，芭芭拉，阿方斯·卡爾

我可以把這個集分成大小相同的兩個子集。由連續的字符「AL」定義的子集中1將是

艾倫，阿爾弗雷德，阿爾

子集2由連續的字符定義的AR將是

拉里，巴巴拉，卡爾。

我正在尋找一種算法，可以對任何任意字符串進行此操作。得到的子集集合不必等於2，但它應該是最小集合，並且結果子集應該大致相等。

Elliott

Answer 1

看一看http://en.wikipedia.org/wiki/Suffix_array。有可能你真正想要做的是爲每個文檔創建一個後綴數組，並且它們將所有後綴數組合併到一起，並將指針返回到原始版本，以便您可以通過查找字符串作爲數組中的後綴。

Answer 2

這很棘手。我想知道是否有更高的目標（如單詞索引）還是僅僅是一個學術問題？

除非您接受由空序列定義的單個集合（出現在所有單詞中）的小數解，否則它通常是不可解的。例如，取字符串：a,ab,b。

1. a必須進入由a定義的集合。
2. b必須進入由b定義的集合。
3. ab必須進入兩者，因爲它包含兩個子序列。

您正在處理的單詞是否會出現類似的例子？我不知道。也許你可以把文字映射到多個集合，或者你可以有一個打破平局的系統來決定把它放在哪裏。

假設這不是問題，burrows-wheeler transform可能有助於找到良好的子字符串。

或者怎麼樣是這樣的：

1. 生成的單詞的所有序列。
2. 構建子序列的干涉圖，如果它們都出現在單個單詞中，則邊連接兩個子序列。
3. 爲圖表着色。
4. 爲每種顏色選擇一個代表性的子序列。
5. 做一個由每個代表性的子序列定義的集合。如果該顏色的所有單詞都有該子字符串，則將它們全部放入該集合中。
6. 否則，刪除，從圖中串，並從步驟重複3

這種算法可能破裂，但它可能給你一些想法有關的溶液（或的trickiness至少一些知道你的題 ;-）。