Fuzzy string search(ntz-develop.blogspot.com)
ntz-develop.blogspot.com
Fuzzy string search
http://ntz-develop.blogspot.com/2011/03/fuzzy-string-search.html
7 comments
Yes, its useful for alignment. However, I've noticed that such alignment techniques are quite slow (since many of them resort to brute force on O(n^2) on sufficiently large strings - a few thousand maybe).
I've found that a better way to approach this problem is to use suffix arrays to generate the best overlaps (ranges) from the reference and then perform a "range compression" (not of the audible kind) to coalesce adjacent ranges that differ by very little and insert/delete the offending characters.
I'm using a similar technique for genome compression against a reference and am able to get a 700x compression on 2 Korean genomes and 130x compression on hg18(build 36.1) and another build/assembly(number 36.3) of the human reference genome.
I've found that a better way to approach this problem is to use suffix arrays to generate the best overlaps (ranges) from the reference and then perform a "range compression" (not of the audible kind) to coalesce adjacent ranges that differ by very little and insert/delete the offending characters.
I'm using a similar technique for genome compression against a reference and am able to get a 700x compression on 2 Korean genomes and 130x compression on hg18(build 36.1) and another build/assembly(number 36.3) of the human reference genome.
I have been working on a Ternary Search Trie implementation for Python on and off for a while. This is definitely a good read for some other methods for fuzzy string search. The benefits of the TST (versus other Trie formulations) is summarized on my blog.[1] I think I will do a follow up post covering their characteristics in comparison to the methods Nikita covered in this post.
The author mentions at the end that he didn't consider Tries. However, I think they are valuable data structure.
[1] http://blog.hackthology.com/ternary-search-tries-for-fast-fl...
The author mentions at the end that he didn't consider Tries. However, I think they are valuable data structure.
[1] http://blog.hackthology.com/ternary-search-tries-for-fast-fl...
REF: http://code.google.com/p/fuzzy-search-tools/
For those that don't make it all the way through the article, the author has implemented all the algorithms in Java and is available at his project page (above).
For those that don't make it all the way through the article, the author has implemented all the algorithms in Java and is available at his project page (above).
i've used Damerau–Levenshtein + Jaro-Winkler for database record matching/customer dedupe. these things work magic. found 2x as many matches vs exact comparison.
I'm currently using a Patricia trie in an open source project I'm working on, still pretty new to trees / tries but now that I have begun to use them I can see how widely used they are in a lot of modern software products
We use aho-corasick to extract keywords from terabyte size corpus. Works really well but you have to build your matching tree before.
Just thought I'd mention it because if you find it interesting, computational biology is a real growth area right now - the cost of sequencing genomes has been dropping faster than Moore's law, and it's quite possible that within our lifetimes we will be using this sort of technology to genetically engineer people.