Lucene Fuzzy Search: BK-Tree can improve performance 3-20 times. [LUCENE-2230]

W. Burkhard and R. Keller. Some approaches to best-match file searching, CACM, 1973
http://portal.acm.org/citation.cfm?doid=362003.362025

I was inspired by http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees (Nick Johnson, Google).

Additionally, simplified algorythm at http://www.catalysoft.com/articles/StrikeAMatch.html seems to be much more logically correct than Levenstein distance, and it is 3-5 times faster (isolated tests).

Big list od distance implementations:
http://www.dcs.shef.ac.uk/\~sam/stringmetrics.htm

---
Migrated from [LUCENE-2230](https://issues.apache.org/jira/browse/LUCENE-2230) by Fuad Efendi, updated May 17 2011
Environment:
```
Lucene currently uses brute force full-terms scanner and calculates distance for each term. New BKTree structure improves performance in average 20 times when distance is 1, and 3 times when distance is 3. I tested with index size several millions docs, and 250,000 terms.
New algo uses integer distances between objects.
```

Attachments: [BKTree.java](https://apache.github.io/lucene-jira-archive/attachments/LUCENE-2230/BKTree.java), [Distance.java](https://apache.github.io/lucene-jira-archive/attachments/LUCENE-2230/Distance.java), [DistanceImpl.java](https://apache.github.io/lucene-jira-archive/attachments/LUCENE-2230/DistanceImpl.java), [FuzzyTermEnumNEW.java](https://apache.github.io/lucene-jira-archive/attachments/LUCENE-2230/FuzzyTermEnumNEW.java) (versions: 2)

Start by reviewing the attached BKTree.java, Distance.java, DistanceImpl.java, and FuzzyTermEnumNEW.java files, then locate Lucene’s current brute-force fuzzy-term search path. Compare matching and distance behavior, and establish benchmarks using the reported index and term sizes. Done means an agreed implementation with validated search behavior and measured performance improvement.

Written by the indexing model from the issue text.