AppString > AppStringDoc

Common

Introduction

This module provides the core functionality for approximate string search. It includes similarity metrics, gram generators and the query class.

Overview

1. We support the following similarity functions / distance measures:
   • Levenshtein Distance (aka the Edit Distance) http://en.wikipedia.org/wiki/Levenshtein_distance
   • Jaccard Similarity http://en.wikipedia.org/wiki/Jaccard_Similarity_Coefficient
   • Cosine Similarity http://en.wikipedia.org/wiki/Cosine_similarity
   • Dice Similarity http://en.wikipedia.org/wiki/Dice%27s_coefficient

2. We support generation of fixed length grams into various C++ containers, with or without positional information. Grams can be strings or hashed strings (hashed to an unsigned int).

3. The query class contains the query string, similarity measure, similarity threshold, etc.

Contributors

• Alexander Behm (design, implementation)
• Chen Li (design, project leader)
• Jiaheng Lu (implementation)
• Rares Vernica (design, main author)
• Shengyue Ji (design, implementation)