字符串压缩 - 将每个字符串压缩为唯一的子字符串标识符。算法运行时间太长。
大家好
我正在两个数据集的字符串标识符之间构建人行横道。因此，我尝试将两个数据集中的字符串“压缩”为具有唯一标识它们的最少字符数的子字符串。
例如，考虑以下数据集：
| 原始ID | 压缩ID |
|---|---|
| 苹果 | 苹果 |
| 阿法 | pph |
| 苹果 | 苹果 |
| 应用程序 | pps |
| 阿尔法 | lp，阿尔 |
| 苹果 | 是 |
在此示例中，Apples 被压缩为“es”，因为没有其他 id 包含“es”，并且“es”在此类唯一子字符串中具有最少的字符数。
此外，Alpha 被压缩为“lp”和“Al”，用 (,) 分隔，因为它们具有相同的字符数。
这个想法是使用这些压缩字符串并在两个数据集上应用包含标准来生成人行横道。
我考虑过以下简单的算法来获取这些最低字符的唯一子字符串：对于每个字符串，获取每个子字符串。检查每个字符串的每个子字符串是否存在于其他地方（以便它是另一个字符串的子字符串），如果不存在（因此它是唯一的），请注意该唯一子字符串的字符长度。现在，选择每个字符串中字符数最少的子字符串。
这是我为实现上述算法而编写的Python代码：
def get_substrings(string):
"""Generate all substrings of a string."""
substrings = set()
for i in range(len(string)):
for j in range(i + 1, len(string) + 1):
substrings.add(string[i:j])
return substrings
def preprocess_dataset(dataset):
"""Generate all substrings for each string in the dataset."""
all_substrings = {}
for string in dataset:
all_substrings[string] = get_substrings(string)
return all_substrings
def get_minimal_unique_substrings(string, all_substrings):
min_length = len(string)
minimal_substrings = []
for substring in all_substrings[string]:
if all(substring not in all_substrings[other_string] for other_string in all_substrings if other_string != string):
if len(substring) < min_length:
min_length = len(substring)
minimal_substrings = [substring]
elif len(substring) == min_length and substring not in minimal_substrings:
minimal_substrings.append(substring)
return ",".join(set(minimal_substrings))
然而，问题是，考虑到我的数据集包含大约 7000 万个观测值，这段代码运行起来需要太多时间。我想知道是否有人对上述算法有替代建议，或者关于如何加快算法速度的任何建议。我也欢迎您对其他字符串压缩方法的意见。
谢谢！任何提示和帮助将不胜感激。最美好的祝愿。
最终编辑：修复了上表中的压缩 ID 输出。
这是一个有趣的问题。起初，它看起来是 NP 难的，因为至少有 n！从输入单词 W 到可能的缩写 A 的映射。至少，因为一个缩写是完整的单词，根本没有缩写 + 每个单词的单词的所有子串！
假设 W 中输入单词的平均长度为 k，则 A 的大小约为 n * k^2。因此映射的数量为 (n * k^2) * (n * k^2 - 1) * (n * k^2 - 2) * … * (n * k^2 - n) >= n!。
并且您希望找到最佳映射，即所有输入单词上每个指定缩写的长度之和尽可能最小的映射。在您的表格示例中，该值为 19。
但这实际上可以在多项式时间内解决。这是解决方案。
您首先需要一组“允许的”缩写。这些缩写不会与其他输入单词冲突并且是唯一的。在您的示例中，例如 pps 或 pple，而不是 pp。这可以通过创建一个空字典来构造。然后迭代每个输入单词 w_i \in W、所有输入单词，并生成 w_i 所有可能的缩写。如果存在，则将值加1，如果不存在，则将其值设置为1。关键是缩写。迭代所有输入单词后，您将得到一个大小为 O(n * l^2) 的字典，其中 l 是最长输入单词的大小。建造它也需要同样的时间。现在将这个字典转换为 set，它只包含值等于 1 的缩写。这样您就消除了所有重复的缩写，只留下允许的缩写。我们称这个集合为 A*。
现在再次迭代 W 中的所有 w_i \，并再次迭代 w_i 的所有缩写 a_i。从最短的开始 - 仅一个字母，仅两个字母，...，w_i。检查 a_i 是否在 A* 中。如果是这样，则将 w_i 映射到 a_i。 A*中至少有一个a_i，即假设W中的单词是唯一的情况下的整个w_i。由于我们尝试使用最短的缩写，因此 A* 中找到的第一个缩写是 w_i 允许的最短缩写。继续W中的所有单词。
您最终会得到最佳的映射。它是有效的，因为我们映射到 A* 的缩写，它们是唯一的并且不会与任何两个单词发生冲突。 A* 的构造方式暗示了这一点。并且映射是最优的。因为我们总是将 w_i 映射到允许的最短缩写。
我们设法在 O(3 * n * l^2) ~ O(n * l^2) 中找到这个映射，如果 l，最大输入字长是常数，O(n)。
PS：我刚刚意识到输入单词是唯一的还不够，它也不能包含互为子串的输入单词。在你的例子中，那就是苹果和苹果。您有 apple for apple 作为缩写，但这不是唯一的子字符串。 Apples 也有子字符串 apple。您希望如何处理此案？在这种情况下，在我提出的解决方案中，apple 不会有唯一的缩写，因为它不存在，因此每个 w_i 至少有一个 a_i 的说法，即 w_i 不成立。