python - 需要关于分词算法的帮助

Question

我有一个字母子列表列表，其中每个子列表中的字母数量可能会有所不同。列表和子列表是有序的。这个结构可以用来生成单词，方法是选择一个数字 X，从每​​个子列表中的 X 位置取一个字母，然后按顺序连接它们。如果数字 X 大于子列表的长度，它将环绕。

给定一组单词，我需要找到一种方法将它们打包成这种尽可能小的结构(即具有最短的子列表)。当然，子列表的数量必须与最长单词中的字母数量一样多，而较短的单词将由空格/空格填充。

我不是 CS 毕业生，所以如果问题的描述不完全清楚，我深表歉意。举个简单的例子:假设我有单词 [ 'a', 'an', 'if', 'is', 'in', 'on', 'of', 'i'] 我需要打包，我可以使用以下结构:

[  
    [ 'i', 'o', 'a' ],  
    [ 's', 'n', 'f', ' ' ]  
]

这将使我能够产生以下单词:

0: is  
1: on  
2: af*  
3: i  
4: os*  
5: an  
6: if  
7: o *  
8: as*  
9: in  
10: of  
11: a

例如，如果您占据位置 10，则单词“of”是通过将第一个子列表中索引 10 % 3 (= 1) 处的字母与索引 10 % 4 (= 2) 处的字母连接起来生成的) 来自第二个子列表。

到目前为止，我最好的尝试是使用汉明距离矩阵首先放置“连接最多”的单词，然后是它们最近的邻居，目的是尽量减少每次插入时的变化。这是一个完全直观的尝试，我觉得必须有更好/更智能的方法来解决这个问题。

澄清

这是我正在尝试解决的一个实际问题，约束条件(大致)如下:
1.每个子列表的字符数应在100以内。
2. keyspace 应该尽可能小(即虚假词的数量应该最少)。粗略地说，数百万个选项中的一个键空间是临界的。

我什至不知道是否有可能为此提供一个好的解决方案。例如，使用我现在拥有的算法，我可以在 150 万个选项的键空间中插入大约 200 个单词(只是随机的英语单词)。我想做得更好。

Answer 1

嗯，你说你对次优解决方案感兴趣，所以我给你一个。它取决于字母表的大小。例如，对于 26 数组大小将略高于 100(无论要编码的字数如何)。

众所周知，如果您有两个不同的素数 a和 b和非负整数 k和 l ( k < a , l < b )，您可以找到号码 n那n % a == k和 n % b == l .
例如，使用 ( a = 7, a = 13, k = 6, l = 3 ) 您可以使用 n = 7 * 13 + 7 * 3 + 13 * 6 . n % 7 == 6和 n % 13 == 3

同样适用于任意数量的素数。

你可以像这样初始化数组。

['a', 'b', 'c', ... 'z', 'z', 'z', 'z', ...]   # array size = 29
['a', 'b', 'c', ... 'z', 'z', 'z', 'z', ...]   # array size = 31
['a', 'b', 'c', ... 'z', 'z', 'z', 'z', ...]   # array size = 37
['a', 'b', 'c', ... 'z', 'z', 'z', 'z', ...]   # array size = 41
...

现在，假设您的词是“极客”。为此，您需要数字 X，例如 X % 29 == 6 , X % 31 == 4 , X % 37 == 4 , X % 41 == 10 .而且你总能找到这样的 X，如上所示。

因此，如果您有 26 个字母的字母表，则可以创建宽度为 149 的矩阵(请参阅素数列表)并用它对任何单词进行编码。