A better similarity ranking algorithm for variable length strings

by

Simon White of Catalysoft wrote an article about a very clever algorithm that compares adjacent character pairs that works really well for my purposes:

http://www.catalysoft.com/articles/StrikeAMatch.html

Simon has a Java version of the algorithm and below I wrote a PL/Ruby version of it (taken from the plain ruby version done in the related forum entry comment by Mark Wong-VanHaren) so that I can use it in my PostgreSQL queries:

CREATE FUNCTION string_similarity(str1 varchar, str2 varchar)
RETURNS float8 AS '

str1.downcase! 
pairs1 = (0..str1.length-2).collect {|i| str1[i,2]}.reject {
  |pair| pair.include? " "}
str2.downcase! 
pairs2 = (0..str2.length-2).collect {|i| str2[i,2]}.reject {
  |pair| pair.include? " "}
union = pairs1.size + pairs2.size 
intersection = 0 
pairs1.each do |p1| 
  0.upto(pairs2.size-1) do |i| 
    if p1 == pairs2[i] 
      intersection += 1 
      pairs2.slice!(i) 
      break 
    end 
  end 
end 
(2.0 * intersection) / union

' LANGUAGE 'plruby';

Works like a charm!

More Related Contents:

  1. How can I match fuzzy match strings from two datasets?
  2. Efficient string matching in Apache Spark
  3. Javascript fuzzy search that makes sense
  4. Find the similarity metric between two strings
  5. Filter multiple values on a string column in dplyr
  6. PowerShell and the -contains operator
  7. How to calculate distance similarity measure of given 2 strings?
  8. Checking images for similarity with OpenCV
  9. Fuzzy string search library in Java [closed]
  10. How do I do a fuzzy match of company names in MYSQL with PHP for auto-complete?
  11. how to compute similarity between two strings in MYSQL
  12. High performance fuzzy string comparison in Python, use Levenshtein or difflib [closed]
  13. Comparing strings with tolerance
  14. Regex for existence of some words whose order doesn’t matter
  15. Find cosine similarity between two arrays
  16. Apply fuzzy matching across a dataframe column and save results in a new column
  17. Efficient method to calculate the rank vector of a list in Python
  18. String similarity with Python + Sqlite (Levenshtein distance / edit distance)
  19. R fuzzy string match to return specific column based on matched string
  20. get cosine similarity between two documents in lucene
  21. Check whether a string contains a substring
  22. Checking fuzzy/approximate substring existing in a longer string, in Python?
  23. How to select R data.table rows based on substring match (a la SQL like)
  24. Remove ends of string entries in pandas DataFrame column
  25. How to compute jaccard similarity from a pandas dataframe
  26. Comparison-based ranking algorithm
  27. MySQL update statement to store ranking positions
  28. Is it possible to use fzf (command line fuzzy finder) with windows 10 git-bash?
  29. Hamming Distance / Similarity searches in a database
  30. Find matching strings between two vectors in R

Leave a Comment