4

假设我有文本“abcabx”。我想知道有一个重复的模式“ab”,它出现的所有位置,以及这些重复的上下文如何与它的其他出现相关。我还希望数据结构具有区分和隔离的独特模式“c”和“x”。我已经设置了一个后缀树来尝试这样做,它看起来像这样(来自this SO answer):

abcabx

这确实告诉我模式“ab”出现了两次,一次带有后缀“cabx”,另一次带有“x”。但是,根处的“ab”仅指向模式的第一次出现。它的叶子“cabx”中还嵌入了另一个“ab”,当我希望那个“ab”(在“cabx”中)以某种方式被确认为数据结构中的重复时。我知道根“ab”的“x”叶代表它,但我需要知道,在“ab”的“cabx”叶中,那里有一个“ab”。另外,两个独特的图案“c”和“x”是该边缘的一部分。加上它们在那个边缘的位置,以及它们的“主要定义”(根边缘?)之间的交叉引用。

更简单地说,数据结构需要清楚地说明“这是所有独特的模式”,“这是所有重复的模式以及它们发生的每个地方”,以及“这是关联所有这些事物的上下文” .

所以我想我正在为后缀树寻找一个类似图形的元素,它将划分出已知的模式并将它们明确地关联起来。在此过程中,将记录独特的模式。但是我还是想要后缀树的上下文特征,比如说“c”(不是“cabx”,而是“c”)和“x”都在“ab”之后,“abx”在“abc”之后,什么跟在他们之后(在更大的情况下)等等。是否有后缀树的改编可以做到这一点,或者可能是另一种算法?

4

1 回答 1

1

后缀树基本上只是以一种便于搜索子字符串的方式存储字符串的所有后缀。每个重复多次的子串将对应一个非终端节点。找到模式出现的上下文相对容易——如果你计算每个分支中的符号数量,它会给你从序列末尾开始的子字符串的偏移量,例如,有两个分支ab,长度为 1 和长度为 4 之一,因此您知道该模式从字符串末尾开始出现 3 和 6 个符号,或者从开头开始出现 3 和 0。

于 2012-09-07T14:02:42.440 回答