Ruby/Rails字典应用程序- 6个字母的单词查找器，由两个较小的单词连接而成

Question

我需要创建将处理字典(dictionary.txt文件)的功能。目标是找到所有由两个较小的单词连接而成的六个字母的单词，例如:

con + vex => convex
tail + or => tailor
we + aver => weaver

当然，文件中可能有一些单词长度不超过6个字母，但可以使用一个简单的方法轻松筛选出这些单词:

def cleanup_file
file_data = File.read('dictrionary.txt').split
file_data.reject! { |word| word.size < 6 }
end

但是现在问题来了——如何发现数组中的其他字符串是否由两个相连的小单词组成?

[编辑]

示例dictionary.txt文件在这里

Answer 1

考虑只是在一个伪代码解决方案，但你应该:

• 迭代字典的每一行，并根据每个单词的长度将单词存储在6个不同的数组中。
  • 确保所有的单词都是小写的，没有重复的，所有的值都是排序的，所以以后你可以在数组中正确地使用.bsearch。
• 迭代长度为6的数组(例如convex)，并在长度为1的数组(对于给定的示例是c)和长度为5的数组(onvex)中查找当前单词的第一个字符的匹配。如果有匹配，就省省吧。
  • 然后继续在长度-2和长度-4数组中寻找匹配(co和nvex相应)并保存匹配。
  • 最后，在length-3数组(con和vex)中查看字符串的两个部分，并保存任何匹配
  • 查找下一个6个字符的字符串，直到完成。

很可能有更好的方法来解决这个问题，比如在第一次迭代中使用.bsearch_index在其相应的数组中插入每个单词进行排序，而不是在同一迭代中插入重复项，但大部分工作负载将在第二次迭代中进行，二进制搜索在O(log n)时间内工作，所以我想它应该足够快。

Answer 2

假设字典如下:

dictionary = [
"a", "abased", "act", "action", "animal", "ape", "apeman",
"art", "assertion", "bar", "barbed", "barhop", "based", "be",
"become", "bed", "come", "hop", "ion", "man"
]

我假设，像大多数字典一样，dictionary是排序的。

首先计算下面的哈希值。

by_len = dictionary.each_with_object({}) do |w,h|
len = w.length
(h[len] ||= []) << w if len < 7
end    
#=> {1=>["a"],
#    6=>["abased", "action", "animal", "apeman", "barbed",
#        "barhop", "become"],
#    3=>["act", "ape", "art", "bar", "bed", "hop", "ion", "man"],
#    5=>["based"],
#    2=>["be"],
#    4=>["come"]}

每个键是一个字长(1-6)，每个值是dictionary中长度为键值的字数组。

接下来，我将定义一个辅助函数，根据给定的单词数组(list)是否包含给定的单词(word)返回true或false。

def found?(list, word)
w = list.bsearch { |w| w >= word }
w && w == word
end

例如:

found?(by_len[3], "art")
#=> true
found?(by_len[3], "any")
#=> false

看到数组# bsearch。

我们现在提取感兴趣的词:

by_len[6].select { |w| (1..5).any? { |i|
found?(by_len[i], w[0,i]) && found?(by_len[6-i], w[i..-1]) } }
#=> ["abased", "action", "apeman", "barbed", "barhop", "become"]