Uploaded image for project: 'Lucene - Core'
  1. Lucene - Core
  2. LUCENE-3662

extend LevenshteinAutomata to support transpositions as primitive edits

    Details

    • Type: New Feature
    • Status: Closed
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: 4.0-ALPHA
    • Fix Version/s: 4.0-ALPHA
    • Component/s: None
    • Labels:
      None
    • Lucene Fields:
      New

      Description

      This would be a nice improvement for spell correction: currently a transposition counts as 2 edits,
      which means users of DirectSpellChecker must use larger values of n (e.g. 2 instead of 1) and
      larger priority queue sizes, plus some sort of re-ranking with another distance measure for good results.

      Instead if we can integrate "chapter 7" of http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.652
      then you can just build an alternative DFA where a transposition is only a single edit
      (http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance)

      According to the benchmarks in the original paper, the performance for LevT looks to be very similar to Lev.

      Support for this is now in moman (https://bitbucket.org/jpbarrette/moman/) thanks to Jean-Philippe
      Barrette-LaPierre.

        Attachments

        1. update-moman.patch
          18 kB
          Robert Muir
        2. lev1.rev115.txt
          4 kB
          Robert Muir
        3. lev1.rev119.txt
          3 kB
          Robert Muir
        4. lev1t.txt
          4 kB
          Robert Muir
        5. LUCENE-3662_upgrade_moman.patch
          14 kB
          Robert Muir
        6. LUCENE-3662.patch
          34 kB
          Robert Muir
        7. LUCENE-3662.patch
          37 kB
          Robert Muir
        8. LUCENE-3662.patch
          48 kB
          Robert Muir
        9. LUCENE-3662.patch
          48 kB
          Robert Muir
        10. LUCENE-3662.patch
          53 kB
          Robert Muir

          Activity

            People

            • Assignee:
              Unassigned
              Reporter:
              rcmuir Robert Muir
            • Votes:
              0 Vote for this issue
              Watchers:
              0 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved: