Home arrow Development Cycles arrow Page 5 - How to Strike a Match
DEVELOPMENT CYCLES

How to Strike a Match


In a previous article, Tame the Beast by Matching Similar Strings, I presented a brief survey of approximate string matching algorithms, and argued their importance for information retrieval tasks. A classic example of information retrieval using similarity searching is entering a keyword into the search string box on Amazon’s web site in order to retrieve descriptions of products related to that keyword. Approximate string matching algorithms can be classified as equivalence algorithms and similarity ranking algorithms. In this article, I present a new similarity ranking algorithm, together with its associated string similarity metric. I also include Java source code, so you can easily incorporate the algorithm into your own applications.

Author Info:
By: Simon White
Rating: 5 stars5 stars5 stars5 stars5 stars / 39
April 07, 2004
TABLE OF CONTENTS:
  1. · How to Strike a Match
  2. · The New Metric
  3. · A Real World Example
  4. · A Java Implementation
  5. · Finishing the Java Implementation
  6. · Summary

print this article
SEARCH DEVARTICLES

How to Strike a Match - Finishing the Java Implementation
(Page 5 of 6 )

Taking Account of White Space

This method uses the split() method of the String class to split the input string into separate words, or tokens. It then iterates through each of the words, computing the character pairs for each word. The character pairs are added to an ArrayList, which is returned from the method. An ArrayList is used, rather than an array, because we do not know in advance how many character pairs will be returned. (At this point, the program doesn’t know how much white space the input string contains.)


/** @return an ArrayList of 2-character Strings. */
   
private static ArrayList wordLetterPairs(String str) {
       ArrayList allPairs 
= new ArrayList();
       
// Tokenize the string and put the tokens/words into an array 
       String[] words = str.split("s");
       // For each word
       for (int w=0; w < words.length; w++) {
           // Find the pairs of characters
           String[] pairsInWord = letterPairs(words[w]);
           for (int p=0; p < pairsInWord.length; p++) {
               allPairs.add(pairsInWord[p]);
           }
       }
       return allPairs;
   }

Computing the Metric

This public method computes the character pairs from the words of each of the two input strings, then iterates through the ArrayLists to find the size of the intersection. Note that whenever a match is found, that character pair is removed from the second array list to prevent us from matching against the same character pair multiple times. (Otherwise, ‘GGGGG’ would score a perfect match against ‘GG’.)


/** @return lexical similarity value in the range [0,1] */
   
public static double compareStrings(String str1String str2) {
       ArrayList pairs1 
wordLetterPairs(str1.toUpperCase());
       ArrayList pairs2 
wordLetterPairs(str2.toUpperCase());
       int intersection 
0;
       int union 
pairs1.size() + pairs2.size();
       
for (int i=0i<pairs1.size(); i++) {
           Object pair1
=pairs1.get(i);
           
for(int j=0j<pairs2.size(); j++) {
               Object pair2
=pairs2.get(j);
               
if (pair1.equals(pair2)) {
                   intersection
++;
                   pairs2
.remove(j);
                   
break;
               
}
           
}
       
}
       
return (2.0*intersection)/union;
   
}


blog comments powered by Disqus
DEVELOPMENT CYCLES ARTICLES

- Division of Large Numbers
- Branch and Bound Algorithm Technique
- Dynamic Programming Algorithm Technique
- Genetic Algorithm Techniques
- Greedy Strategy as an Algorithm Technique
- Divide and Conquer Algorithm Technique
- The Backtracking Algorithm Technique
- More Pattern Matching Algorithms: B-M
- Pattern Matching Algorithms Demystified: KMP
- Coding Standards
- A Peek into the Future: Transactional Memory
- Learning About the Graph Construct using Gam...
- Learning About the Graph Construct using Gam...
- Learning About the Graph Construct using Gam...
- How to Strike a Match

Watch our Tech Videos 
Dev Articles Forums 
 RSS  Articles
 RSS  Forums
 RSS  All Feeds
Write For Us 
Weekly Newsletter
 
Developer Updates  
Free Website Content 
Contact Us 
Site Map 
Privacy Policy 
Support 

Developer Shed Affiliates

 




© 2003-2017 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap
Popular Web Development Topics
All Web Development Tutorials