我怎样才能加速这个Anagram算法

Question

我正在制作一个移动应用程序来查找字谜和部分匹配.移动很重要,因为没有大量的计算能力,效率是关键.

该算法采用任意数量的字母,包括重复,并找到由其字母组成的最长的单词,每个字母只使用一次.我也很想快速找到最好的结果,只要N满足,我就不会真正关注底部(较短的).例如:

STACK => stack, tacks, acts, cask, cast, cats…

我已经做了一些谷歌搜索,并找到了一些算法,我想出了一个我认为有效的,但效率不如我想的那样.

我有一个预制的查找字典,它将排序的键映射到生成该键的真实单词.

"aelpp" => ["apple", "appel", "pepla"]

我根据键的长度进一步将每个字典拆分成不同的字典.所以5个字母长的键在一个字典中,6个键在另一个字典中.这些字典中的每一个都在一个数组中,其中索引是在字典中找到的键的长度.

anagramArray[5] => dictionary5
dictionary5["aelpp"] => ["apple", "appel", "pepla"]

我的算法首先输入一个输入词" lappe",然后对其进行排序:

"lappe" => "aelpp"

现在,对于每个包含最多5个字母内容的字典,我会进行比较以将其拉出来.这是伪代码:

word = input.sort
for (i = word.length; i > 0; i--)
    dictionaryN = array[i]
    for (key in dictionaryN)
        if word matches key
            add to returnArray
        end
    end
    if returnArray count > N
      break
    end
end

returnArray.sort by longest word, alphabetize

字典中只有大约170,000个单词,但12个字母输入的搜索最多需要20秒.我的match方法从键中取出正则表达式:

"ackst" => /a.*c.*k.*s.*t.*/

例如,一个4个字母的键,如acst(act),将匹配ackst(堆栈),因为:

"ackst" matches /a.*c.*s.*t.*/

我看到其他应用程序在更短的时间内做同样的事情,我想知道我的方法是垃圾还是只需要一些调整.

如何从单词生成前N个字谜中获得最大计算效率,按最大长度排序？

Answer 1

如果你想到(甚至可能代表)字典作为字母树,你可以避免看到很多节点.如果"stack"在字典中,那么将存在从根到标记为ackst的叶子的路径.如果输入的单词是"攻击",那么将其排序以获得aackstt.您可以编写一个递归例程来跟踪从根目录下来的链接,随时使用来自aackstt的字母.当你到达ack时,你的字符串中会留下stt​​,所以你可以按照s来达到ackst,但你可以排除跟随你到达acku及其后代,v到达ackv及其后代,依此类推.

事实上,使用这种方案,你可以只使用一棵树来保存任意数量字母的单词,这可以节省你多次搜索,每个目标长度一次.