如何编写一个方法来计算ruby中字符串中最常见的子字符串？
我有一个类DNA的程序。 该程序计算字符串中最常见的k-mer。 因此，它正在寻找长度为k的字符串中最常见的子字符串。
一个例子是创建一个带有AACCAATCCG字符串的dna1对象。 count k-mer方法将查找长度为k的子字符串并输出最常见的答案。 因此，如果我们设置k = 1，那么’A’和’C’将是字符串中出现次数最多的因为它出现了四次。 见下面的例子：
dna1 = DNA.new('AACCAATCCG') => AACCAATCCG >> dna1.count_kmer(1) => [#, 4] >> dna1.count_kmer(2) => [#, 2] 这是我的DNA课程：
class DNA def initialize (nucleotide) @nucleotide = nucleotide end def length @nucleotide.length end protected attr_reader :nucleotide end
这是我想要实现的计数kmer方法：
# I have k as my only parameter because I want to pass the nucleotide string in the method def count_kmer(k) # I created an array as it seems like a good way to split up the nucleotide string. counts = [] #this tries to count how many kmers of length k there are num_kmers = self.nucleotide.length- k + 1 #this should try and look over the kmer start positions for i in num_kmers #Slice the string, so that way we can get the kmer kmer = self.nucleotide.split('') end #add kmer if its not present if !kmer = counts counts[kmer] = 0 #increment the count for kmer counts[kmer] +=1 end #return the final count return counts end #end dna class end
我不确定我的方法出了什么问题。
码
def most_frequent_substrings(str, k) (0..str.size-k).each_with_object({}) do |i,h| b = [] str[i..-1].scan(Regexp.new str[i,k]) { b << Regexp.last_match.begin(0) + i } (h[b.size] ||= []) << b end.max_by(&:first).last.each_with_object({}) { |a,h| h[str[a.first,k]] = a } end
例
str = "ABBABABBABCATSABBABB" most_frequent_substrings(str, 4) #=> {"ABBA"=>[0, 5, 14], "BBAB"=>[1, 6, 15]}
这表明str最常出现的4字符子串出现3次。 有两个这样的子串：“ABBA”和“BBAB”。 “ABBA”开始于偏移（进入str ）0,5和14，“BBAB”子串开始于偏移1,6和15。
说明
对于上面的例子，步骤如下。
k = 4 n = str.size - k #=> 20 - 4 => 16 e = (0..n).each_with_object([]) #
我们可以通过将它转换为数组来查看此枚举器将生成的值。
e.to_a #=> [[0, []], [1, []], [2, []], [3, []], [4, []], [5, []], [6, []], [7, []], [8, []], # [9, []], [10, []], [11, []], [12, []], [13, []], [14, []], [15, []], [16, []]]
请注意，在构建数组时，将修改每个元素中包含的空数组。 继续， e的第一个元素传递给块，块变量使用并行赋值分配 ：
i,a = e.next #=> [0, []] i #=> 0 a #=> []
我们现在考虑从str偏移i #=> 0开始的大小为4的子字符串，它被视为“ABBA”。 现在执行块计算。
b = [] r = Regexp.new str[i,k] #=> Regexp.new str[0,4] #=> Regexp.new "ABBA" #=> /ABAB/ str[i..-1].scan(r) { b << Regexp.last_match.begin(0) + i } #=> "ABBABABBABCATSABBABB".scan(r) { b << Regexp.last_match.begin(0) + i } b #=> [0, 5, 14]
我们接下来有
(h[b.size] ||= []) << b
变成了
(h[b.size] = h[b.size] || []) << b #=> (h[3] = h[3] || []) << [0, 5, 14]
由于h没有键3 ，右侧的h[3]等于nil 。 继续，
#=> (h[3] = nil || []) << [0, 5, 14] #=> (h[3] = []) << [0, 5, 14] h #=> { 3=>[[0, 5, 14]] }
请注意，我们丢弃了scan的返回值。 我们所需要的只是b
这告诉我们“ str ”在str出现三次，从偏移0,5和14开始。
现在观察
e.to_a #=> [[0, [[0, 5, 14]]], [1, [[0, 5, 14]]], [2, [[0, 5, 14]]], # ... # [16, [[0, 5, 14]]]]
在e所有元素都传递给块之后，块返回
h #=> {3=>[[0, 5, 14], [1, 6, 15]], # 1=>[[2], [3], [7], [8], [9], [10], [11], [12], [13], [14], [15], [16]], # 2=>[[4, 16], [5, 14], [6, 15]]}
考虑只出现一次的子串： h[1] 。 其中之一是[2] 。 这适用于从str offset 2开始的4个字符的子字符串：
str[2,4] #=> "BABA"
这被发现是该子串的唯一实例。 类似地，在出现两次的子串中有str[4,4] = str[16,4] #=> "BABB", given by h[2][0] #=> [4, 16] 。
接下来，我们确定长度为4的子字符串的最大频率：
c = h.max_by(&:first) #=> [3, [[0, 5, 14], [1, 6, 15]]]
（也可以写成c = h.max_by { |k,_| k } ）。
d = c.last #=> [[0, 5, 14], [1, 6, 15]]
为方便起见，将d转换为哈希：
d.each_with_object({}) { |a,h| h[str[a.first,k]] = a } #=> {"ABBA"=>[0, 5, 14], "BBAB"=>[1, 6, 15]}
并从方法返回该哈希值。
值得一提的是一个细节。 d可能包含两个或多个引用相同子字符串的数组，在这种情况下，关联键（子字符串）的值将等于这些数组的最后一个。 这是一个简单的例子。
str = "AAA" k = 2
在这种情况下，上面的数组d将相等
d = [[0], [1]]
这两个参考str[0,2] #=> str[1,2] #=> "AA" 。 在构建哈希时，第一个被第二个覆盖：
d.each_with_object({}) { |a,h| h[str[a.first,k]] = a } #=> {"AA"=>[1]}
像这样的东西？
require 'set' def count_kmer(k) max_kmers = kmers(k) .each_with_object(Hash.new(0)) { |value, count| count[value] += 1 } .group_by { |_,v| v } .max [Set.new(max_kmers[1].map { |e| e[0] }), max_kmers[0]] end def kmers(k) nucleotide.chars.each_cons(k).map(&:join) end
编辑：这是该课程的全文：
require 'set' class DNA def initialize (nucleotide) @nucleotide = nucleotide end def length @nucleotide.length end def count_kmer(k) max_kmers = kmers(k) .each_with_object(Hash.new(0)) { |value, count| count[value] += 1 } .group_by { |_,v| v } .max [Set.new(max_kmers[1].map { |e| e[0] }), max_kmers[0]] end def kmers(k) nucleotide.chars.each_cons(k).map(&:join) end protected attr_reader :nucleotide end
这使用Ruby 2.2.1使用您指定的类和方法生成以下输出：
>> dna1 = DNA.new('AACCAATCCG') => # >> dna1.count_kmer(1) => [#, 4] >> dna1.count_kmer(2) => [# , 2]
作为奖励，您还可以：
>> dna1.kmers(2) => ["AA", "AC", "CC", "CA", "AA", "AT", "TC", "CC", "CG"]