Home arrow Development Cycles arrow Page 4 - 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 - A Java Implementation
(Page 4 of 6 )

In this section, I describe an implementation of the similarity algorithm in Java. The code is not difficult to understand, so if Java is not your main programming language, it should not be a big task to translate it to your favourite language.

Overview

I have implemented the algorithm as a single class with three static methods. Two of those methods are private, so only one, compareStrings(), is exposed to users of the class. Here is the outline of the class, with the bodies of the methods removed:


import java.util.ArrayList;
public class 
LetterPairSimilarity {
   
public static double compareStrings(String str1String str2) {}
   
private static ArrayList wordLetterPairs(String str) {}
   
private static String[] letterPairs(String str) {}
}

Until now, I have not discussed how I deal with white space in the input strings. My approach is to dismiss from consideration any character pairs that include white space. In effect, this means first finding the words (or tokens) in your input strings before looking for adjacent character pairs. You can now see how this approach maps to the methods outlined above. CompareStrings() calls wordLetterPairs() for each of its inputs. WordLetterPairs() identifies the words in its input string, and uses the method letterPairs() to compute the pairs of adjacent characters in each of those words. When compareStrings() has collected the character pairs for each of its input strings, it computes the return value according to the similarity metric.
I will now discuss the bodies of the methods in detail, in a bottom-up order.

Computing Letter Pairs

The basis of the algorithm is the method that computes the pairs of characters contained in the input string. This method creates an array of Strings to contain its result. It then iterates through the input string, to extract character pairs and store them in the array. Finally, the array is returned.


/** @return an array of adjacent letter pairs contained in the input string */
   
private static String[] letterPairs(String str) {
       int numPairs 
str.length()-1;
       String
[] pairs = new String[numPairs];
       
for (int i=0i<numPairsi++) {
           pairs
[i] = str.substring(i,i+2);
       
}
       
return pairs;
   
}


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