c++ - 在单词词典中获取以片段开头/包含/结尾的单词

Question

假设我们具有英语词典中所有A-Z词典单词的列表。

我有三种情况要对这些单词列表执行：

1）找出所有以“特定片段”开头的单词

eg: If my fragment is 'car', word 'card' should be returned

2）找出“包含”该片段的所有单词作为子字符串

eg: If my fragment is 'ace', word 'facebook' should be returned

3）找出所有以“特定片段”结尾的单词

eg: If my fragment is 'age', word 'image' should be returned

在互联网上进行一些搜索后，我发现1）可以通过trie /压缩的trie完成，3）可以通过后缀树完成。

我不确定2）如何实现。
再加上是否有可以处理所有这三种情况的更好方案？由于同时维护前缀树和后缀树可能是一项占用大量内存的任务。

请让我知道其他需要注意的地方。

提前致谢。

PS：我将使用C ++实现这一目标

编辑1：目前，在这里，我在巨大的帮助下构建了一个后缀树。

Single Word Suffix Tree Generation in C Language

在这里，我需要为整个英语词典单词构建一个后缀树。所以我应该创建一个

a）每个单词都有单独的后缀树或

b）为所有单词创建一个通用的后缀树。

我不确定在a）情况下子串匹配时如何跟踪每个单词的单个树

有指针吗？

Answer 1

正如我在评论中指出的那样，前缀和后缀大小写由常规子字符串大小写（＃2）覆盖。根据定义，所有前缀和后缀也是子字符串。因此，我们需要解决的只是一般的子字符串问题。

由于您有静态字典，因此可以相对容易地将其预处理为一种可以快速查询子字符串的形式。您可以使用后缀树来执行此操作，但是构造和处理简单排序的平面数据向量要容易得多，所以这就是我将在此处描述的内容。

因此，最终目标是要有一个排序的子词列表，以便可以进行二进制搜索来找到匹配项。

首先，请注意，为了找到与查询片段匹配的最长子串，不必列出每个单词的所有可能子串，而只需列出所有可能的后缀。这是因为所有子字符串都只能视为后缀的前缀。 （知道吗？第一次遇到它有点令人费解，但最终很简单，非常有用。）

因此，如果生成每个词典词的所有后缀，然后对它们全部进行排序，则足以在任何词典词中找到任何特定的子字符串：对后缀进行二进制搜索以找到下限（std::lower_bound） -以查询片段开头的第一个后缀。然后找到上限（std::upper_bound）-这将是最后一个以查询片段开头的后缀。 [lower，upper []范围内的所有后缀都必须以查询片段开头，因此，这些后缀最初来自的所有单词都包含查询片段。

现在，很明显，实际上拼出所有后缀会占用大量内存-但您不需要。后缀可以仅视为单词的索引-后缀开始的偏移量。因此，每个可能的后缀只需要一对整数：一个用于（原始）单词索引，一个用于该单词中后缀的索引。 （您可以根据字典的大小将两者巧妙地打包在一起，以节省更多空间。）

总而言之，您需要做的是：


生成所有单词的所有单词后缀索引对的数组。
根据它们的语义含义将它们排序为后缀（不是数值）。我建议使用自定义比较器std::stable_sort。这是最长的步骤，但由于字典是静态的，因此可以脱机一次完成。
对于给定的查询片段，在排序的后缀索引中找到上下限。此范围内的每个后缀都对应一个匹配的子字符串（查询长度，从单词索引的单词后缀索引开始）。请注意，某些单词可能不止一次匹配，甚至可能重叠。




为了澄清，这是由单词“臭鼬”和“奶酪”组成的字典的一个小例子。

“臭鼬”的后缀是“臭鼬”，“ kunk”，“ unk”，“ nk”和“ k”。以索引表示，它们是0, 1, 2, 3, 4。 “奶酪”的后缀是“奶酪”，“ heese”，“ eese”，“ ese”，“ se”和“ e”。索引为0, 1, 2, 3, 4, 5。

由于“臭鼬”是我们非常有限的虚构字典中的第一个单词，因此我们将其分配为索引0。“奶酪”位于索引1。因此，最后的后缀为：0:0, 0:1, 0:2, 0:3, 0:4, 1:0, 1:1, 1:2, 1:3, 1:4, 1:5。

对这些后缀进行排序将产生以下后缀字典（我添加了实际对应的文本子字符串，仅用于说明）：

0  | 0:0 | cheese
1  | 0:5 | e
2  | 0:2 | eese
3  | 0:3 | ese
4  | 0:1 | heese
5  | 1:4 | k
6  | 1:1 | kunk
7  | 1:3 | nk
8  | 0:4 | se
9  | 1:0 | skunk
10 | 1:2 | unk

考虑查询片段“ e”。下限为1，因为“ e”是大于或等于查询“ e”的第一个后缀。上限是4，因为4（“ heese”）是大于“ e”的第一个后缀。因此，后缀1、2和3均以查询开头，因此，它们全部来自的单词都将查询作为子字符串包含（在后缀索引处，表示查询的长度）。在这种情况下，所有这三个后缀都以不同的偏移量属于“奶酪”。

请注意，对于不是任何单词的子字符串（例如本例中的“ a”）的查询片段，都没有匹配项；在这种情况下，上下限将相等。