3

我有一大串字符串。我想将字符串分成子集，这样：

  1. 子集中的每个项目共享 1 个或多个连续字符。
  2. 定义子集的共享连续字符对于子集集是唯一的（即，共享字符足以定义与其他子集互斥关系的字符串子集）。
  3. 子集的大小大致相同。
  4. 生成的子集集是满足上述标准所需的最小子集数。

例如，给定以下一组名称：

艾伦、拉里、阿尔弗雷德、芭芭拉、阿尔方斯、卡尔

我可以将这个集合分成两个大小相等的子集。由连续字符“AL”定义的子集 1 将是

艾伦、阿尔弗雷德、阿尔方斯

由连续字符 ar 定义的子集 2 将是

拉里、芭芭拉、卡尔。

我正在寻找一种可以对任意字符串集执行此操作的算法。子集的结果集不必等于 2，但它应该是最小集，并且结果子集应该近似相等。

艾略特

4

2 回答 2

2

这很棘手。我想知道是否有更高的目的（比如词索引）或者这只是一个学术问题？

一般来说，它是不可解的，除非您接受由空序列定义的单个集合的平凡解（它出现在所有单词中）。例如，获取字符串：a, ab, b.

  1. a必须进入由 定义的集合a。
  2. b必须进入由 定义的集合b。
  3. ab必须进入两者，因为它包含两个子序列。

你正在处理的单词会出现类似的例子吗？我不知道。也许您可以处理映射到多个集合的单词，或者您可以拥有一个打破平局的系统来确定放置它的位置。

假设这不是问题，burrows-wheeler 变换可能有助于找到好的子串。

或者怎么样：

  1. 生成单词中的所有子序列。
  2. 构建子序列的干扰图，如果两个子序列都出现在一个单词中，则用一条边连接它们。
  3. 为图表着色。
  4. 为每种颜色选择一个有代表性的子序列。
  5. 制作一个由每个代表性子序列定义的集合。如果该颜色的所有单词都具有该子字符串，则将它们全部放入该集合中。
  6. 否则，从图中删除该子字符串，然后从步骤 3 开始重复。

该算法可能已损坏，但它可能会给您一些关于解决方案的想法（或者至少对您的问题的棘手性有一些想法；-）。

于 2012-04-05T01:33:17.923 回答
2

看看http://en.wikipedia.org/wiki/Suffix_array。您真正想要做的可能是为每个文档创建一个后缀数组，然后它们合并所有后缀数组，并带有指向原始版本的指针，这样您就可以通过查找将集合作为一个字符串来搜索因为它作为数组中的后缀。

于 2012-04-05T04:24:45.773 回答