查找字符串中所有重复的子字符串以及它们出现的频率

Problem:

我需要满足以下条件的所有字符序列：

1. 字符序列必须出现多次（(LE, 1) 因此无效）。
2. 字符序列必须长于 1 个字符（因此 ((M, 2) 无效）。
3. 字符序列不得是出现相同次数的较长现有序列的一部分（因此，如果 (LIO, 2) 存在，则 (LI, 2) 无效）。

因此，如果输入字符串是：KAKAMNENENELIOLELIONEM$输出将是：

(KA, 2)
(NE, 4)
(LIO, 2)

它还需要速度快，应该能够在合理的时间内解决 1000 个字符长的字符串。

我尝试过的：

从后缀树获取分支数量：

Editing this后缀树创建库（Python-Suffix-Tree），我制作了一个程序，给出了一些错误的结果。

我将此函数添加到 suffix_tree.py 中的 SuffixTree 类中：

def get_repeated_substrings(self):
    curr_index = self.N
    values = self.edges.values()
    values = sorted(values, key=lambda x: x.dest_node_index)
    data = []  # index = edge.dest_node_index - 1
    for edge in values:
        if edge.source_node_index == -1:
            continue
        top = min(curr_index, edge.last_char_index)
        data.append([edge.source_node_index,
                self.string[edge.first_char_index:top+1]])
    repeated_substrings = {}
    source_node_indexes = [i[0] for i in data]
    nodes_pointed_to = set(source_node_indexes)
    nodes_pointed_to.remove(0)
    for node_pointed_to in nodes_pointed_to:
        presence = source_node_indexes.count(node_pointed_to)
        key = data[node_pointed_to-1][1]
        if key not in repeated_substrings:
            repeated_substrings[key] = 0
        repeated_substrings[key] += presence
    for key in repeated_substrings:
        if len(key) > 1:
            print(key, repeated_substrings[key])

然后像这样使用它和库的其余部分：

from lib.suffix_tree import SuffixTree

st = SuffixTree("KAKANENENELIOLELIONE$")
print(st.get_repeated_substrings())

Output:

KA 2
NE 7
LIO 2
IO 4

get_repeated_substrings() 基本上遍历节点之间的所有连接（在这个库中称为边），并保存它指向的节点还有多少个连接（将其保存到repeated_substrings），然后打印保存的超过一个字符的值长的。

它将连接数附加到该序列已有的连接数上，这在大多数情况下都有效，但正如您在上面的输出中看到的，它导致“NE”的值不正确（7，它应该是4).解决这个问题后，我意识到该方法无法检测由相同字符（AA，BB）组成的图案，以及其他故障。我的结论：要么没有办法用后缀树解决它，要么我做的事情非常错误。

其他方法：

我还尝试了一些更直接的方法，包括循环遍历内容，但这也没有成功：

import copy

string = 'kakabaliosie'

for main_char in set(string):
    indices = []
    for char_i, char in enumerate(string):
        if main_char == char:
            indices.append(char_i)
    relative = 1
    while True
        for index in indices:
            other_indices = copy.deepcopy(indices)
            other_indices.remove(index)
            for other_index in other_indices:

（无法完成它）

问题：

我怎样才能编写一个程序来实现我想要的功能？

您的后缀树方法是正确的方法。

获取匹配集及其出现次数

基本上你需要做的是以 BFS 方式遍历树。从根的子节点开始，您将递归地计算每个节点可到达的叶数。这将导致一种方法Node您可以在根上调用它。这是一个可能的实现：

def count_leaves(self, stree):
    leaves_count = 0
    for child in [stree.nodes[x.dest_node_index] for x in self.edges.values()]:
        child_leaves_count = child.count_leaves(stree)
        if 0 == child_leaves_count:
            # The child node is a leaf...
            leaves_count = leaves_count + 1
        else:
            # The child node is an internal node, we add up the number of leaves it can reach
            leaves_count = leaves_count + child_leaves_count
    self.leaves_count = leaves_count
    return leaves_count

现在，每个节点都标有它可以到达的叶子数量。

然后，后缀树的有趣属性将帮助您自动过滤掉不符合您的某些要求的子字符串：

• 如果一个字符串只出现一次，那么您必然最终会过渡到叶节点（所述过渡至少有两个字符，因为我们不计算结束标记$）。这意味着它不是一个明确的状态，因此我们甚至不考虑它。
• 如果我们有 (LI, 2) 和 (LIO, 2)，那么 (LI, 2) 是后缀树的隐式状态，这意味着它位于边的中间。由于我们只考虑具有显式状态的子串（即最终位于节点中的子串），因此我们一开始就找不到 (LI, 2)。
• 内部节点至少有 2 个子节点，否则它们将是叶子但没有。

现在，迭代内部节点将为您提供子字符串列表及其在输入字符串中出现的次数（您需要过滤掉表示 1 个字符子字符串的节点）。

您将在下面找到输入字符串的后缀树的字符串表示形式。这将帮助您可视化哪些子字符串是匹配的。

- O - N E M $ - ##  
    - L E L I O N E M $ - ##  
- I O - N E M $ - ##  
      - L E L I O N E M $ - ##  
- $ - ##  
- E - M $ - ##  
      L I O - N E M $ - ##
              L E L I O N E M $ - ##
      N E - L I O L E L I O N E M $ - ##
            N E L I O L E L I O N E M $ - ##
- K A - M N E N E N E L I O L E L I O N E M $ - ##
        K A M N E N E N E L I O L E L I O N E M $ - ##
- L - E L I O N E M $ - ##
      I O - N E M $ - ##
            L E L I O N E M $ - ##
- A - M N E N E N E L I O L E L I O N E M $ - ##
      K A M N E N E N E L I O L E L I O N E M $ - ##
- M - $ - ##
      N E N E N E L I O L E L I O N E M $ - ##
- N E - M $ - ##
        L I O L E L I O N E M $ - ##
        N E - L I O L E L I O N E M $ - ##
              N E L I O L E L I O N E M $ - ##

这将导致以下输出：

(IO, 2)
（埃利奥，2）
（埃内伊，2）
（卡，2）
（利奥，2）
（东北，4）
（内内，2）

排除固定出现次数 (N) 的冗余匹配

我们现在假设LIO, and IO应该被过滤掉，因为，就像ELIO，他们有两场比赛。较大匹配的此类子字符串将被称为“冗余匹配”。以下难题仍未解决：给定恰好出现 N 次的所有匹配项的集合N 场比赛（其中N是一个固定整数），我们如何过滤掉“冗余”的呢？

我们首先从按长度递减排序的 N 匹配集创建一个优先级队列。然后我们将迭代地构建广义后缀树 (GST）这些匹配来识别冗余匹配。为此，算法如下：

1. For each element in the heap (taken at the top), test if this element is a substring of one of the elements already registered in the GST
   • 如果没有：将其插入GST并将其附加到“良好匹配”列表中。
   • 否则：跳过它，因为已经注册了另一个更大的匹配项......并尝试使用下一个元素
2. 一旦堆为空，好的匹配列表将包含所有非冗余 N 匹配.

这导致以下伪 Python 代码：

match_heap = heapify(set_of_matches)
good_matches = []
match_gst = generalized_suffix_tree()
while (not match_heap.empty()):
    top_match = match_heap.top()
    if (not match_gst.is_substring(top_match.string)):
        gst_match.insert(top_match.string)
        good_matches.append(top_match)
    else:
        # The given match is a substring of an already registered, bigger match
        # We skip it
return good_matches

过滤所有冗余匹配

现在我们可以过滤冗余匹配N 场比赛，很容易从我们的全局匹配集中过滤掉所有这些。我们使用匹配项的出现次数将匹配项收集到存储桶中，然后将上一节的算法应用于每个存储桶。

Notes

为了实现上面的算法，你需要有一个广义后缀树实现，这与常规后缀树有点不同。如果您找不到 Python 实现，您可以随时采用已有的实现。看这个问题以获得有关如何操作的提示。