blocks|key|189836|text|我给你找到了这个：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|189837|def+levenshtein_distance(s,+t)
++m+=+s.length
++n+=+t.length
++return+m+if+n+==+0
++return+n+if+m+==+0
++d+=+Array.new(m%2B1)+{Array.new(n%2B1)}

++(0..m).each+{%7Ci%7C+d[i][0]+=+i}
++(0..n).each+{%7Cj%7C+d[0][j]+=+j}
++(1..n).each+do+%7Cj%7C
++++(1..m).each+do+%7Ci%7C
++++++d[i][j]+=+if+s[i-1]+==+t[j-1]++#+adjust+index+into+string
++++++++++++++++++d[i-1][j-1]+++++++#+no+operation+required
++++++++++++++++else
++++++++++++++++++[+d[i-1][j]%2B1,++++#+deletion
++++++++++++++++++++d[i][j-1]%2B1,++++#+insertion
++++++++++++++++++++d[i-1][j-1]%2B1,++#+substitution
++++++++++++++++++].min
++++++++++++++++end
++++end
++end
++d[m][n]
end

[+['fire','water'],+['amazing','horse'],+["bamerindos",+"giromba"]+].each+do+%7Cs,t%7C
++puts+"levenshtein_distance('#{s}',+'#{t}')+=+#{levenshtein_distance(s,+t)}"
end|code-block|syntax|javascript|189838|这是很棒的输出：=)|189839|levenshtein_distance('fire',+'water')+=+4
levenshtein_distance('amazing',+'horse')+=+7
levenshtein_distance('bamerindos',+'giromba')+=+9|189840|来源：http://rosettacode.org/wiki/Levenshtein_distance#Ruby|offset|length|189841|entityMap|0|LINK|mutability|MUTABLE|url|http://rosettacode.org/wiki/Levenshtein_distance#Ruby^0|0|0|0|0|3|1H|0|0^^$0|@$1|2|3|4|5|6|7|W|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|X|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|Y|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|Z|8|@]|9|@]|A|$E|F]]|$1|K|3|L|5|6|7|10|8|@]|9|@$M|11|N|12|1|13]]|A|$]]|$1|O|3|-4|5|6|7|14|8|@]|9|@]|A|$]]]|P|$Q|$5|R|S|T|A|$U|V]]]]

I found this for you:

<pre><code>def levenshtein_distance(s, t)
 m = s.length
 n = t.length
 return m if n == 0
 return n if m == 0
 d = Array.new(m+1) {Array.new(n+1)}

 (0..m).each {|i| d[i][0] = i}
 (0..n).each {|j| d[0][j] = j}
 (1..n).each do |j|
 (1..m).each do |i|
 d[i][j] = if s[i-1] == t[j-1] # adjust index into string
 d[i-1][j-1] # no operation required
 else
 [ d[i-1][j]+1, # deletion
 d[i][j-1]+1, # insertion
 d[i-1][j-1]+1, # substitution
 ].min
 end
 end
 end
 d[m][n]
end

[ ['fire','water'], ['amazing','horse'], ["bamerindos", "giromba"] ].each do |s,t|
 puts "levenshtein_distance('#{s}', '#{t}') = #{levenshtein_distance(s, t)}"
end
</code></pre>

That's awesome output: =)

<pre><code>levenshtein_distance('fire', 'water') = 4
levenshtein_distance('amazing', 'horse') = 7
levenshtein_distance('bamerindos', 'giromba') = 9
</code></pre>

Source: <a href="http://rosettacode.org/wiki/Levenshtein_distance#Ruby" rel="noreferrer">http://rosettacode.org/wiki/Levenshtein_distance#Ruby</a>

blocks|key|3022640|text|简单得多，我有时是一个Ruby卖弄的人…|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3022641|#+Levenshtein+distance,+translated+from+wikipedia+pseudocode+by+ross

def+lev+s,+t
++return+t.size+if+s.empty?
++return+s.size+if+t.empty?
++return+[+(lev+s.chop,+t)+%2B+1,
+++++++++++(lev+s,+t.chop)+%2B+1,
+++++++++++(lev+s.chop,+t.chop)+%2B+(s[-1,+1]+==+t[-1,+1]+?+0+:+1)
+++++++].min
end|code-block|syntax|javascript|3022642|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Much simpler, I'm a Ruby show-off at times...

<pre><code># Levenshtein distance, translated from wikipedia pseudocode by ross

def lev s, t
 return t.size if s.empty?
 return s.size if t.empty?
 return [ (lev s.chop, t) + 1,
 (lev s, t.chop) + 1,
 (lev s.chop, t.chop) + (s[-1, 1] == t[-1, 1] ? 0 : 1)
 ].min
end
</code></pre>

blocks|key|2809992|text|由于原生C语言的绑定，更容易和更快：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2809993|gem+install+levenshtein-ffi
gem+install+levenshtein

require+'levenshtein'

Levenshtein.normalized_distance+string1,+string2,+threshold|code-block|syntax|javascript|2809994|http://rubygems.org/gems/levenshtein+http://rubydoc.info/gems/levenshtein/0.2.2/frames|offset|length|2809995|entityMap|0|LINK|mutability|MUTABLE|url|http://rubygems.org/gems/levenshtein|1|http://rubydoc.info/gems/levenshtein/0.2.2/frames^0|0|0|0|10|0|11|1D|1|0^^$0|@$1|2|3|4|5|6|7|U|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|V|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|W|8|@]|9|@$I|X|J|Y|1|Z]|$I|10|J|11|1|12]]|A|$]]|$1|K|3|-4|5|6|7|13|8|@]|9|@]|A|$]]]|L|$M|$5|N|O|P|A|$Q|R]]|S|$5|N|O|P|A|$Q|T]]]]

Much easier and fast due to native C binding:

<pre><code>gem install levenshtein-ffi
gem install levenshtein

require 'levenshtein'

Levenshtein.normalized_distance string1, string2, threshold
</code></pre>

<a href="http://rubygems.org/gems/levenshtein">http://rubygems.org/gems/levenshtein</a>
<a href="http://rubydoc.info/gems/levenshtein/0.2.2/frames">http://rubydoc.info/gems/levenshtein/0.2.2/frames</a>

blocks|key|189853|text|我做了一个damerau-levenshtein+gem，其中的算法是用C语言实现的|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|189854|require+"damerau-levenshtein"
dl+=+DamerauLevenshtein
dl.distance("Something",+"Smoething")+#returns+1|code-block|syntax|javascript|189855|entityMap|0|LINK|mutability|MUTABLE|url|https://github.com/GlobalNamesArchitecture/damerau-levenshtein^0|5|N|0|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@$A|R|B|S|1|T]]|C|$]]|$1|D|3|E|5|F|7|U|8|@]|9|@]|C|$G|H]]|$1|I|3|-4|5|6|7|V|8|@]|9|@]|C|$]]]|J|$K|$5|L|M|N|C|$O|P]]]]

I made a <a href="https://github.com/GlobalNamesArchitecture/damerau-levenshtein" rel="noreferrer">damerau-levenshtein gem</a> where algorithms are implemented in C

<pre><code>require "damerau-levenshtein"
dl = DamerauLevenshtein
dl.distance("Something", "Smoething") #returns 1
</code></pre>

blocks|key|2810021|text|Rubygems中有一个实用方法，它实际上应该是公共的，但无论如何都不是：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2810022|require+"rubygems/text"
ld+=+Class.new.extend(Gem::Text).method(:levenshtein_distance)

p+ld.call("asd",+"sdf")+=>+2|code-block|syntax|javascript|2810023|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

There is an utility method in Rubygems that actually should be public but it's not, anyway:

<pre><code>require "rubygems/text"
ld = Class.new.extend(Gem::Text).method(:levenshtein_distance)

p ld.call("asd", "sdf") =&gt; 2
</code></pre>

blocks|key|187759|text|我喜欢上面DigitalRoss的解决方案。然而，正如dawg所指出的那样，它的运行时在order+O(3%5En)上增长，这对于更长的字符串来说并不是很好。使用memoization或“动态编程”可以显著加快该解决方案的速度：|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|187760|def+lev(string1,+string2,+memo={})
++return+memo[[string1,+string2]]+if+memo[[string1,+string2]]
++return+string2.size+if+string1.empty?
++return+string1.size+if+string2.empty?
++min+=+[+lev(string1.chop,+string2,+memo)+%2B+1,
++++++++++lev(string1,+string2.chop,+memo)+%2B+1,
++++++++++lev(string1.chop,+string2.chop,+memo)+%2B+(string1[-1]+==+string2[-1]+?+0+:+1)
+++++++].min
++memo[[string1,+string2]]+=+min
++min
end|code-block|syntax|javascript|187761|然后我们就有了更好的运行时，(我认为它几乎是线性的？我不是很确定)。|187762|[9]+pry(main)>+require+'benchmark'
=>+true
[10]+pry(main)>+@memo+=+{}
=>+{}
[11]+pry(main)>+Benchmark.realtime{puts+lev("Hello+darkness+my+old+friend",+"I've+come+to+talk+with+you+again")}
26
=>+0.007071999832987785|187763|entityMap^0|1E|6|0|0|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@$9|R|A|S|B|C]]|D|@]|E|$]]|$1|F|3|G|5|H|7|T|8|@]|D|@]|E|$I|J]]|$1|K|3|L|5|6|7|U|8|@]|D|@]|E|$]]|$1|M|3|N|5|H|7|V|8|@]|D|@]|E|$I|J]]|$1|O|3|-4|5|6|7|W|8|@]|D|@]|E|$]]]|P|$]]

I like DigitalRoss' solution above. However, as pointed out by dawg, its runtime grows on the order <code>O(3^n)</code>, which is no good for longer strings. 
That solution can be sped up significantly using memoization, or 'dynamic programming':

<pre><code>def lev(string1, string2, memo={})
 return memo[[string1, string2]] if memo[[string1, string2]]
 return string2.size if string1.empty?
 return string1.size if string2.empty?
 min = [ lev(string1.chop, string2, memo) + 1,
 lev(string1, string2.chop, memo) + 1,
 lev(string1.chop, string2.chop, memo) + (string1[-1] == string2[-1] ? 0 : 1)
 ].min
 memo[[string1, string2]] = min
 min
end
</code></pre>

We then have much better runtime, (I think it's almost linear? I'm not really sure). 

<pre><code>[9] pry(main)&gt; require 'benchmark'
=&gt; true
[10] pry(main)&gt; @memo = {}
=&gt; {}
[11] pry(main)&gt; Benchmark.realtime{puts lev("Hello darkness my old friend", "I've come to talk with you again")}
26
=&gt; 0.007071999832987785
</code></pre>

blocks|key|2810064|text|Ruby2.3及更高版本附带了包含DidYouMean::Levenshtein.distance的did_you_mean+gem。适合大多数情况，默认情况下可用。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|2810065|DidYouMean::Levenshtein.distance("Test",+"est")+#+=>+1|code-block|syntax|javascript|2810066|entityMap|0|LINK|mutability|MUTABLE|url|https://github.com/ruby/did_you_mean/blob/fbe5aaaae8405d19dc1bf691c5bead6348c6da10/lib/did_you_mean/levenshtein.rb|1|https://github.com/ruby/did_you_mean^0|H|W|1E|C|H|W|0|1E|G|1|0|0^^$0|@$1|2|3|4|5|6|7|U|8|@$9|V|A|W|B|C]|$9|X|A|Y|B|C]]|D|@$9|Z|A|10|1|11]|$9|12|A|13|1|14]]|E|$]]|$1|F|3|G|5|H|7|15|8|@]|D|@]|E|$I|J]]|$1|K|3|-4|5|6|7|16|8|@]|D|@]|E|$]]]|L|$M|$5|N|O|P|E|$Q|R]]|S|$5|N|O|P|E|$Q|T]]]]

Ruby 2.3 and later ship with the <a href="https://github.com/ruby/did_you_mean" rel="noreferrer"><code>did_you_mean</code> gem</a> which includes <a href="https://github.com/ruby/did_you_mean/blob/fbe5aaaae8405d19dc1bf691c5bead6348c6da10/lib/did_you_mean/levenshtein.rb" rel="noreferrer"><code>DidYouMean::Levenshtein.distance</code></a>. Fit for most cases and available by default.
<pre class="lang-rb prettyprint-override"><code>DidYouMean::Levenshtein.distance(&quot;Test&quot;, &quot;est&quot;) # =&gt; 1
</code></pre>

Can I measure the distance between two strings with Ruby?

I.e.:

<pre><code>compare('Test', 'est') # Returns 1
compare('Test', 'Tes') # Returns 1
compare('Test', 'Tast') # Returns 1
compare('Test', 'Taste') # Returns 2
compare('Test', 'tazT') # Returns 5
</code></pre>

Measure the distance between two strings with Ruby?

我可以用Ruby测量两个字符串之间的距离吗？I.e.:compare('Test', 'est') # Returns 1compare('Test', 'Tes') # Returns 1compare('Test', 'Tast') # Returns 1compare('Test', 'Taste') # Ret...

问用Ruby测量两个字符串之间的距离？
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问用Ruby测量两个字符串之间的距离？EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问用Ruby测量两个字符串之间的距离？
EN