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

extend LevenshteinAutomata to support transpositions as primitive edits

    XMLWordPrintableJSON

Details

    • New Feature
    • Status: Closed
    • Major
    • Resolution: Fixed
    • 4.0-ALPHA
    • 4.0-ALPHA
    • None
    • None
    • 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. lev1.rev115.txt
          4 kB
          Robert Muir
        2. lev1.rev119.txt
          3 kB
          Robert Muir
        3. lev1t.txt
          4 kB
          Robert Muir
        4. LUCENE-3662_upgrade_moman.patch
          14 kB
          Robert Muir
        5. LUCENE-3662.patch
          53 kB
          Robert Muir
        6. LUCENE-3662.patch
          48 kB
          Robert Muir
        7. LUCENE-3662.patch
          48 kB
          Robert Muir
        8. LUCENE-3662.patch
          37 kB
          Robert Muir
        9. LUCENE-3662.patch
          34 kB
          Robert Muir
        10. update-moman.patch
          18 kB
          Robert Muir

        Activity

          People

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

            Dates

              Created:
              Updated:
              Resolved: