You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@lucene.apache.org by "Robert Muir (Created) (JIRA)" <ji...@apache.org> on 2011/12/21 01:45:30 UTC
[jira] [Created] (LUCENE-3662) extend LevenshteinAutomata to
support transpositions as primitive edits
extend LevenshteinAutomata to support transpositions as primitive edits
-----------------------------------------------------------------------
Key: LUCENE-3662
URL: https://issues.apache.org/jira/browse/LUCENE-3662
Project: Lucene - Java
Issue Type: New Feature
Affects Versions: 4.0
Reporter: Robert Muir
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.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
[jira] [Updated] (LUCENE-3662) extend LevenshteinAutomata to
support transpositions as primitive edits
Posted by "Robert Muir (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-3662?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Robert Muir updated LUCENE-3662:
--------------------------------
Attachment: LUCENE-3662.patch
patch updated to revision 120 of moman, fixing the bug. tests pass now.
> extend LevenshteinAutomata to support transpositions as primitive edits
> -----------------------------------------------------------------------
>
> Key: LUCENE-3662
> URL: https://issues.apache.org/jira/browse/LUCENE-3662
> Project: Lucene - Java
> Issue Type: New Feature
> Affects Versions: 4.0
> Reporter: Robert Muir
> Attachments: LUCENE-3662.patch, LUCENE-3662.patch, LUCENE-3662.patch, LUCENE-3662.patch, LUCENE-3662_upgrade_moman.patch, lev1.rev115.txt, lev1.rev119.txt, lev1t.txt, update-moman.patch
>
>
> 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.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
[jira] [Commented] (LUCENE-3662) extend LevenshteinAutomata to
support transpositions as primitive edits
Posted by "Uwe Schindler (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-3662?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13175910#comment-13175910 ]
Uwe Schindler commented on LUCENE-3662:
---------------------------------------
A nice Xmas present! +1
I think we should send Jean-Philippe some beers, too.
> extend LevenshteinAutomata to support transpositions as primitive edits
> -----------------------------------------------------------------------
>
> Key: LUCENE-3662
> URL: https://issues.apache.org/jira/browse/LUCENE-3662
> Project: Lucene - Java
> Issue Type: New Feature
> Affects Versions: 4.0
> Reporter: Robert Muir
> Attachments: LUCENE-3662.patch, LUCENE-3662.patch, LUCENE-3662.patch, LUCENE-3662.patch, LUCENE-3662.patch, LUCENE-3662_upgrade_moman.patch, lev1.rev115.txt, lev1.rev119.txt, lev1t.txt, update-moman.patch
>
>
> 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.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
[jira] [Commented] (LUCENE-3662) extend LevenshteinAutomata to
support transpositions as primitive edits
Posted by "Uwe Schindler (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-3662?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13173965#comment-13173965 ]
Uwe Schindler commented on LUCENE-3662:
---------------------------------------
How many beers did you need for that?
> extend LevenshteinAutomata to support transpositions as primitive edits
> -----------------------------------------------------------------------
>
> Key: LUCENE-3662
> URL: https://issues.apache.org/jira/browse/LUCENE-3662
> Project: Lucene - Java
> Issue Type: New Feature
> Affects Versions: 4.0
> Reporter: Robert Muir
> Attachments: LUCENE-3662.patch, LUCENE-3662.patch, LUCENE-3662_upgrade_moman.patch, lev1.rev115.txt, lev1.rev119.txt, lev1t.txt, update-moman.patch
>
>
> 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.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
[jira] [Commented] (LUCENE-3662) extend LevenshteinAutomata to
support transpositions as primitive edits
Posted by "Dawid Weiss (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-3662?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13173942#comment-13173942 ]
Dawid Weiss commented on LUCENE-3662:
-------------------------------------
Avanti Robert! :)
> extend LevenshteinAutomata to support transpositions as primitive edits
> -----------------------------------------------------------------------
>
> Key: LUCENE-3662
> URL: https://issues.apache.org/jira/browse/LUCENE-3662
> Project: Lucene - Java
> Issue Type: New Feature
> Affects Versions: 4.0
> Reporter: Robert Muir
> Attachments: LUCENE-3662.patch, LUCENE-3662.patch, LUCENE-3662_upgrade_moman.patch, lev1.rev115.txt, lev1.rev119.txt, lev1t.txt, update-moman.patch
>
>
> 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.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
[jira] [Commented] (LUCENE-3662) extend LevenshteinAutomata to
support transpositions as primitive edits
Posted by "Dawid Weiss (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-3662?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13175937#comment-13175937 ]
Dawid Weiss commented on LUCENE-3662:
-------------------------------------
+1 for beers for Jean-Phillipe.
> extend LevenshteinAutomata to support transpositions as primitive edits
> -----------------------------------------------------------------------
>
> Key: LUCENE-3662
> URL: https://issues.apache.org/jira/browse/LUCENE-3662
> Project: Lucene - Java
> Issue Type: New Feature
> Affects Versions: 4.0
> Reporter: Robert Muir
> Attachments: LUCENE-3662.patch, LUCENE-3662.patch, LUCENE-3662.patch, LUCENE-3662.patch, LUCENE-3662.patch, LUCENE-3662_upgrade_moman.patch, lev1.rev115.txt, lev1.rev119.txt, lev1t.txt, update-moman.patch
>
>
> 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.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
[jira] [Updated] (LUCENE-3662) extend LevenshteinAutomata to
support transpositions as primitive edits
Posted by "Robert Muir (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-3662?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Robert Muir updated LUCENE-3662:
--------------------------------
Attachment: LUCENE-3662.patch
updated patch with tests. this reveals a bug in moman for LevT(2)...
> extend LevenshteinAutomata to support transpositions as primitive edits
> -----------------------------------------------------------------------
>
> Key: LUCENE-3662
> URL: https://issues.apache.org/jira/browse/LUCENE-3662
> Project: Lucene - Java
> Issue Type: New Feature
> Affects Versions: 4.0
> Reporter: Robert Muir
> Attachments: LUCENE-3662.patch, LUCENE-3662.patch, LUCENE-3662.patch, LUCENE-3662_upgrade_moman.patch, lev1.rev115.txt, lev1.rev119.txt, lev1t.txt, update-moman.patch
>
>
> 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.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
[jira] [Commented] (LUCENE-3662) extend LevenshteinAutomata to
support transpositions as primitive edits
Posted by "Mark Miller (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-3662?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13175870#comment-13175870 ]
Mark Miller commented on LUCENE-3662:
-------------------------------------
Sweet. I'd estimate many beers.
> extend LevenshteinAutomata to support transpositions as primitive edits
> -----------------------------------------------------------------------
>
> Key: LUCENE-3662
> URL: https://issues.apache.org/jira/browse/LUCENE-3662
> Project: Lucene - Java
> Issue Type: New Feature
> Affects Versions: 4.0
> Reporter: Robert Muir
> Attachments: LUCENE-3662.patch, LUCENE-3662.patch, LUCENE-3662.patch, LUCENE-3662.patch, LUCENE-3662_upgrade_moman.patch, lev1.rev115.txt, lev1.rev119.txt, lev1t.txt, update-moman.patch
>
>
> 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.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
[jira] [Updated] (LUCENE-3662) extend LevenshteinAutomata to
support transpositions as primitive edits
Posted by "Robert Muir (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-3662?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Robert Muir updated LUCENE-3662:
--------------------------------
Attachment: LUCENE-3662.patch
updated patch, hooking this into LevenshteinAutomata.
I wrote a trivial test for "dog" and it passes... this is promising.
I'll try to come up with a good testing strategy.
> extend LevenshteinAutomata to support transpositions as primitive edits
> -----------------------------------------------------------------------
>
> Key: LUCENE-3662
> URL: https://issues.apache.org/jira/browse/LUCENE-3662
> Project: Lucene - Java
> Issue Type: New Feature
> Affects Versions: 4.0
> Reporter: Robert Muir
> Attachments: LUCENE-3662.patch, LUCENE-3662.patch, LUCENE-3662_upgrade_moman.patch, lev1.rev115.txt, lev1.rev119.txt, lev1t.txt, update-moman.patch
>
>
> 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.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
[jira] [Updated] (LUCENE-3662) extend LevenshteinAutomata to
support transpositions as primitive edits
Posted by "Robert Muir (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-3662?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Robert Muir updated LUCENE-3662:
--------------------------------
Attachment: LUCENE-3662_upgrade_moman.patch
ok i found the bug, it was a (no longer valid) optimization in the parser for this null state case... no longer a problem now.
Tests pass with this patch, which simply upgrades our moman to the latest revision.
>From here we have to modify the code generator to also generate "T" tables, and deal with the new t-position syntax.
> extend LevenshteinAutomata to support transpositions as primitive edits
> -----------------------------------------------------------------------
>
> Key: LUCENE-3662
> URL: https://issues.apache.org/jira/browse/LUCENE-3662
> Project: Lucene - Java
> Issue Type: New Feature
> Affects Versions: 4.0
> Reporter: Robert Muir
> Attachments: LUCENE-3662_upgrade_moman.patch, lev1.rev115.txt, lev1.rev119.txt, lev1t.txt, update-moman.patch
>
>
> 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.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
[jira] [Resolved] (LUCENE-3662) extend LevenshteinAutomata to
support transpositions as primitive edits
Posted by "Robert Muir (Resolved) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-3662?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Robert Muir resolved LUCENE-3662.
---------------------------------
Resolution: Fixed
Fix Version/s: 4.0
> extend LevenshteinAutomata to support transpositions as primitive edits
> -----------------------------------------------------------------------
>
> Key: LUCENE-3662
> URL: https://issues.apache.org/jira/browse/LUCENE-3662
> Project: Lucene - Java
> Issue Type: New Feature
> Affects Versions: 4.0
> Reporter: Robert Muir
> Fix For: 4.0
>
> Attachments: LUCENE-3662.patch, LUCENE-3662.patch, LUCENE-3662.patch, LUCENE-3662.patch, LUCENE-3662.patch, LUCENE-3662_upgrade_moman.patch, lev1.rev115.txt, lev1.rev119.txt, lev1t.txt, update-moman.patch
>
>
> 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.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
[jira] [Updated] (LUCENE-3662) extend LevenshteinAutomata to
support transpositions as primitive edits
Posted by "Robert Muir (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-3662?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Robert Muir updated LUCENE-3662:
--------------------------------
Attachment: LUCENE-3662.patch
patch, hooking this into directspellchecker by default. I think its ready to commit.
I did some rough perf tests, the transpositions costs us nothing. But the suggestions are much more relevant in some situations:
for example, I typed "Wahsington" into the geonames database, asking for top-5 suggestions:
{panel:title=maxEdits=1}
before:
(no suggestions)
after:
||Suggestion||Score||DocFreq||
|Washington|0.9|61|
{panel:title=maxEdits=2}
before:
||Suggestion||Score||DocFreq||
|Washington|0.8|61|
|Warrington|0.8|13|
|Waddington|0.8|10|
|Wallington|0.8|7|
|Watlington|0.8|5|
after:
||Suggestion||Score||DocFreq||
|Washington|0.9|61|
|Warrington|0.8|13|
|Waddington|0.8|10|
|Wallington|0.8|7|
|Watlington|0.8|5|
About the beers: the story is that I made some small progress towards implementing this (https://bitbucket.org/rmuir/moman) with many many beers, but got stuck, Jean-Phillipe merged my commits, emailed me that he is confident he can implement it in 15 hours, and did just that. I found a bug in the test, he fixed it the next day as before... and go figure it looks like the bug might have been in the part I did.
> extend LevenshteinAutomata to support transpositions as primitive edits
> -----------------------------------------------------------------------
>
> Key: LUCENE-3662
> URL: https://issues.apache.org/jira/browse/LUCENE-3662
> Project: Lucene - Java
> Issue Type: New Feature
> Affects Versions: 4.0
> Reporter: Robert Muir
> Attachments: LUCENE-3662.patch, LUCENE-3662.patch, LUCENE-3662.patch, LUCENE-3662.patch, LUCENE-3662.patch, LUCENE-3662_upgrade_moman.patch, lev1.rev115.txt, lev1.rev119.txt, lev1t.txt, update-moman.patch
>
>
> 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.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
[jira] [Updated] (LUCENE-3662) extend LevenshteinAutomata to
support transpositions as primitive edits
Posted by "Robert Muir (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-3662?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Robert Muir updated LUCENE-3662:
--------------------------------
Attachment: update-moman.patch
as a start, i thought we could try upgrading moman, passing 'False' for transpositions (as if you pass true, it uses the extended state notation including t-positions and this really makes our code-generator angry).
But already there is some silly problem (likely in our code generator). I'll attach some files showing how the difference in the moman output changed
> extend LevenshteinAutomata to support transpositions as primitive edits
> -----------------------------------------------------------------------
>
> Key: LUCENE-3662
> URL: https://issues.apache.org/jira/browse/LUCENE-3662
> Project: Lucene - Java
> Issue Type: New Feature
> Affects Versions: 4.0
> Reporter: Robert Muir
> Attachments: update-moman.patch
>
>
> 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.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
[jira] [Updated] (LUCENE-3662) extend LevenshteinAutomata to
support transpositions as primitive edits
Posted by "Robert Muir (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-3662?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Robert Muir updated LUCENE-3662:
--------------------------------
Attachment: lev1t.txt
lev1.rev119.txt
lev1.rev115.txt
here is the before and after... at a glance the changes only seem cosmetic, maybe mike has an idea :)
I attached a lev1T just for fun to show the new notation as well.
> extend LevenshteinAutomata to support transpositions as primitive edits
> -----------------------------------------------------------------------
>
> Key: LUCENE-3662
> URL: https://issues.apache.org/jira/browse/LUCENE-3662
> Project: Lucene - Java
> Issue Type: New Feature
> Affects Versions: 4.0
> Reporter: Robert Muir
> Attachments: lev1.rev115.txt, lev1.rev119.txt, lev1t.txt, update-moman.patch
>
>
> 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.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
[jira] [Updated] (LUCENE-3662) extend LevenshteinAutomata to
support transpositions as primitive edits
Posted by "Robert Muir (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-3662?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Robert Muir updated LUCENE-3662:
--------------------------------
Attachment: LUCENE-3662.patch
updated patch with hacks to the parser and generated Lev1T and Lev2T parametric descriptions... i have no idea if any of this works yet.
> extend LevenshteinAutomata to support transpositions as primitive edits
> -----------------------------------------------------------------------
>
> Key: LUCENE-3662
> URL: https://issues.apache.org/jira/browse/LUCENE-3662
> Project: Lucene - Java
> Issue Type: New Feature
> Affects Versions: 4.0
> Reporter: Robert Muir
> Attachments: LUCENE-3662.patch, LUCENE-3662_upgrade_moman.patch, lev1.rev115.txt, lev1.rev119.txt, lev1t.txt, update-moman.patch
>
>
> 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.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org