我有一个dictionary(约20万字)，按字母顺序排列。我只需要知道在字符串中的任何位置插入character后，字母的string是否仍然可以成为一个单词。换句话说：我需要知道在单词的特定位置插入的哪些字符仍然可以使它成为以后插入的单词。字符串中字母的顺序(如前后)应该保持不变。
我只是认为，如果不使用一些巨大的数据结构或放弃准确性，下降性能(不到半秒)就不可能做到这一点。但是，即使你会牺牲准确性，我也不知道有什么好的方法能给我一个很好的准确性，一个非常非常高的精度(几乎所有可能的纠正都是可能的)，同时又有点平衡。我想知道其他人是否有办法。以下是我认为必要的：
- 访问
dictionary中的每个单词以获得100%的准确度和准确性，或者在速度和准确性之间做出妥协&精度 - 检查您访问的单词是否具有与字符串匹配的正确顺序的
char执行器 - 检查这个单词中是否多了一个字母
有人知道如何在速度和准确性之间取得良好的结合吗现在我有一个数据结构，它可以很快发现某个东西是否是一个单词，所以我想作为最后的手段，只需在随机位置用随机字母查询数据库，然后询问数据结构之后它是否仍然可以变成一个词，但这感觉是一种不平衡的方法，没有固定的时间。
这个问题的措辞方式，几乎就像你在建议答案应该包括一个概率解决方案，比如Bloom过滤器，如果不是用这么多词的话。
然而，我认为，考虑到需求(小于0.5秒，合理的内存使用)，确定性解决方案是可行的，值得尝试实现和优化，而不是满足于不完美的概率解决方案。
假设你有一个字符串，并且你想在该字符串中找到所有可能的单字符插入，这些字符串可以通过进一步的字符插入转换为有效单词，则如果字符串是n个字符长，则存在n+1个可能的插入位置和26个可能的字符。对于其中的每一个，您都需要检查它们是否是有效单词，或者是否可以通过进一步的插入转换为有效单词。乘以一本词典中的20万个条目，这意味着5200万次测试，每次测试都由"这个字符串是否按这个顺序出现在这个词典条目中"组成。如果我们能找到一种"提前"进行大多数测试的方法，这在现代台式机或智能手机上似乎是可以实现的。
在伪码中，基本算法是：
List findPossibleInsertions(String currentString)
{
List list = {};
for(int pos = 0; pos < currentString.length + 1; pos++)
{
for(char c = 'a'; c <= 'z'; c++)
{
String insertedString = insert c into currentString before pos;
if(stringIsImpossible(insertedString))
continue; // high level test whether the string could be turned into a valid word
int64 stringMask = computeStringMask(insertedString);
// the string is not impossible according to the test, but we need to verify that it is actually possible:
for(String s in Dictionary)
{
// check if the string could be turned into s via insertions using a simple mask check to potentially exclude it (but not 100% confirm it):
if((s.mask & stringMask) != stringMask)
continue; // it's not possible to turn insertedString into s via insertions
if(s.length < insertedString.length)
continue; // can't insert chars to make a shorter string
// confirm that is it possible:
if(canMakeStringViaInsertions(insertedString, s)
{
list.add(insertedString); // this is a valid insertion, add to the list
break;
}
}
}
}
}
这给我们留下了3项任务
- 找到一个高级检查，即给定的字符串不可能用于创建任何带有进一步插入的有效单词
- 计算一个掩码，该掩码可用于测试给定字符串是否可以通过插入扩展以创建给定世界，允许假阳性但不允许假阴性
- 明确测试给定的字符串是否可以通过插入来扩展以创建给定的单词，不允许出现假阳性或假阴性
对于第一个任务，我们可以使用预先计算的位掩码来存储某些字符序列是否可以出现在有效单词中(其中任何一个单词之间都可能添加额外的字符)。要存储5个字符的序列，我们需要26*26*26*26=11881376位，即1485172字节。考虑到这将大致等于存储200K个单词所需的存储量(假设平均单词长度为5.1个字符，加上终止null，再加上每个单词的4字节偏移量)，我不认为这算"巨大"。
为3个字符、4个字符和5个字符的每个组合存储一个位字段。
将位字段设置为全零，然后遍历字典。以5个字符为例，对于每个单词，取每个可能的5个字符序列，其中序列中的每个字符都出现在单词序列中的前一个字符之前。例如，单词"pencil"给出了以下5个字符序列：
"encil"
"pncil"
"pecil"
"penil"
"pencl"
"penci"
使用以下公式将这些5个字符的组合添加到位字段：
index = ((s[0]-'a')*(26^4)) + ((s[1]-'a')*(26^3)) + ((s[2]-'a')*(26^2)) + ((s[3]-'a')*26) + (s[4]-'a');
bitfield[index] = 1;
如果字典中所有单词的所有可能的5个字符序列都被添加到比特字段中，这意味着如果一个5个字符的序列出现在字符串中，但没有在比特字段中设置其比特，则意味着不可能通过向字符串插入字符来创建字典中的任何单词，因为字典中没有按该顺序出现这5个字符的条目。因此，无论添加什么字符，都不会产生有效的单词。
对于4个字符和3个字符的位字段，可以重复相同的过程。
要检查字符串是否可以使用位字段扩展到字典中的有效单词，请使用以下函数：
boolean stringIsImpossible(String s)
{
// test against 5 char bitfield:
for(i = 0; i <= s.length - 5; i++)
{
index = ((s[i]-'a')*(26^4)) + ((s[i+1]-'a')*(26^3)) + ((s[i+2]-'a')*(26^2)) + ((s[i+3]-'a')*26) + (s[i+4]-'a');
if(5charBitmask[index] == 0)
return true;
}
if(s.length > 4)
return false;
// test against 4 char bitfield:
for(i = 0; i <= s.length - 4; i++)
{
index = ((s[i]-'a')*(26^3)) + ((s[i+1]-'a')*(26^2)) + ((s[i+2]-'a')*26) + (s[i+3]-'a');
if(4charBitmask[index] == 0)
return true;
}
if(s.length > 3)
return false;
// test against 3 char bitfield:
for(i = 0; i <= s.length - 3; i++)
{
index = ((s[i]-'a')*(26^2)) + ((s[i+1]-'a')*26) + (s[i+2]-'a');
if(3charBitmask[index] == 0)
return true;
}
return false;
}
对于第二个任务，有必要为每个字典单词创建一个位掩码，该掩码可以很容易地用于测试是否可以通过添加字母从现有单词串中创建。这意味着它需要以相同的顺序包含字符串中的所有字母。从逻辑上讲，如果它不包含字符串中的所有字母，那么它就不能同时包含字符串中所有的字母并以相同的顺序包含它们。因此，如果单词包含字母"a"，我们可以通过将位0设置为1来创建位掩码，如果单词含有字母"b"，则设置位1，如果单词载有字母"c"，则设位2，因为并非字符串中的所有字母都出现在字典单词中。
此外，我们可以根据某些字母是否出现在某些其他字母之后，在掩码中设置额外的位。例如，如果字符串中有一个字母"g"，我们可以设置一个bit，然后在某个点上有一个单词"t"。如果在字符串中设置了位，但在目标字中没有设置位，则不能从字符串中生成字。还可以重用位来处理多个字母组合。例如，如果有一个"g"后跟一个"t"，或者有一个"d"后跟一个"j"等，则可以设置一个位。冲突的可能性降低了，因为在有一个'g'后跟一个't'的情况下，"g"one_answers"t"位将被设置，因此与一个单词匹配，该单词后跟一个'd'，可能会在共享位上发生冲突，但是单独的"d"one_answers"j"比特很可能不会被设置。只要没有假阴性，一些假阳性是可以接受的。
计算字符串掩码的函数如下所示：
int64 computeStringMask(String s)
{
int64 mask = 0;
// add individual letters to bitmask:
for(int i = 0; i < s.length; i++)
{
mask |= 1 << (s[i]-'a');
}
// add "followed by" letter combinations to bitmask:
for(int i = 0; i < s.length-1; i++)
{
for(int j = i+1; j < s.length; j++)
{
mask |= 1 << (((((s[i]-'a') * 26) + (s[j]-'a')) % 37) + 26);
}
}
return mask;
}
需要为字典中的每个字符串计算并存储此掩码。
第三项任务：测试给定的字符串是否可以扩展以创建给定的单词，只需检查单词是否包含字符串中的每个字符，顺序正确即可：
boolean canMakeStringViaInsertions(s, word)
{
int i = 0; j = 0;
while(word[j] != 0)
{
if(s[i] == word[j])
{
// match!
i++;
if(s[i] == 0)
return true; // all chars have matched
}
j++;
}
return false;
}
对findPossibleInsertions()函数的进一步优化是将字典划分为多个块，并为块中的每个单词计算字符串掩码，并将其全部"或"。如果根据字符串计算的掩码对块掩码的测试结果为阴性，则块中的任何单词都不需要测试。