java - 在随机字母串中插入字符，但保持成为单词的可能性，没有庞大的数据结构是否可能？

Question

我有一个按字母顺序排列的dictionary（约20万个单词）。我只需要知道在字符串中任何位置插入string acter之后，字母的char是否仍然可以成为单词。换句话说：我需要知道在单词中特定位置插入的哪些字符仍然可以稍后使之成为带有插入词的单词。字符串中字母的顺序（彼此之前或之后）应保持不变。

我只是认为如果不使用一些巨大的数据结构或放弃准确性，下降性能（不到半秒）就不可能实现。但是，即使您要牺牲准确性，我也不知道有什么好的方法可以使我以非常非常高的精度（几乎所有发现的可能的校正实际上都是可能的）获得良好的准确性，并且同时达到某种程度的平衡。我想知道其他人是否有办法。我认为这是必要的：


请访问dictionary中的每个单词以获取100％的准确性和精度，或者在速度，准确性和精度之间进行折衷。
检查您访问的单词是否具有正确的char字符以与字符串匹配。
检查这个单词是否适合附加字母


有谁知道如何在速度和准确性之间取得良好的结合？现在，我有一个数据结构，可以很快地找到某个词，因此，我认为作为最后的选择，只是用随机位置的随机字母查询数据库，并询问该数据结构是否仍然可以之后再说，但这感觉就像是一种不平衡的方式，没有固定的时间。

Answer 1

他们用这种方式来表达这个问题，几乎就像您建议的答案那样，如果不是这么多话，就应该包括一个概率解决方案，例如Bloom过滤器。

但是，我认为确定性解决方案是可行的，因为有必要尝试实现和优化该确定性要求（少于0.5秒，合理的内存使用），而不是为一个不完美的概率解决方案而努力。

假设您有一个字符串，并且想在该字符串中找到所有可能的单个字符插入，这些插入会产生可以转换为有效单词的字符串，并进一步插入该字符，则如果该字符串的长度为n个字符，则存在n + 1个可能的插入位置和26个可能的字符可以在每个位置插入（假定未加重音的英语字母），因此对于9个字符长的字符串将有260个可能的插入。对于这些中的每一个，您都需要检查它们是否是有效词，或者可以通过进一步插入变成有效词。乘以字典中的200K条目，即转换为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 * 26 = 11881376位或1485172字节。鉴于这将大致等于存储20万个单词所需的存储量（假设平均单词长度为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个字符序列，但未在位域中设置其位，则表示它不是可以通过在字符串中插入char来在字典中创建任何单词，因为字典中没有按这5个char顺序出现的条目。因此，无论您添加什么字符，都不会产生有效的单词。

可以对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设置为1，则可以创建位掩码。我们试图查看是否可以通过在字符串中插入字符来制成带有单词的位掩码的字符串，如果结果不等于字符串的位掩码，则无法从中获得单词，因为不是所有的字母字典单词中存在一个字符串。

此外，我们可以根据某些字母是否在某些其他字母之后出现来在掩码中设置额外的位。例如，如果字符串中有字母“ g”，我们可以设置一个位，在此之后的某个时间点，则有字母“ t”。如果在字符串中设置了该位，但在目标字中未设置该位，则无法从字符串中生成该字。还可以重用位来处理多个字母组合。例如，如果有一个“ g”后跟一个“ t”，或者有一个“ d”后跟一个“ j”，则可以设置一个位。减少了碰撞的可能性，因为在有一个“ g”后跟一个“ t”，则将设置“ g”和“ t”位，因此与带有“ d”后跟“ j”的单词匹配，共享位上可能会发生冲突，但很可能不会设置单个的“ d”和“ 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()函数的进一步优化是将字典划分为多个块，并为块中的每个单词计算字符串掩码，或者对它们进行或运算。如果从字符串计算出的掩码相对于块掩码测试为负，则无需测试块中的所有单词。