Can we unify the viterbi search logic in the tokenizers of kuromoji and nori? [LUCENE-10493]

[asfimport]

We now have common dictionary interfaces for kuromoji and nori (#11429). A natural question would be: is it possible to unify the Japanese/Korean tokenizers?

The core methods of the two tokenizers are parse() and backtrace() to calculate the minimum cost path by Viterbi search. I'd set the goal of this issue to factoring out them into a separate class (in analysis-common) that is shared between JapaneseTokenizer and KoreanTokenizer.
The algorithm to solve the minimum cost path itself is of course language-agnostic, so I think it should be theoretically possible; the most difficult part here might be the N-best path calculation - which is supported only by JapaneseTokenizer and not by KoreanTokenizer.

---

Migrated from LUCENE-10493 by Tomoko Uchida (@mocobeta), resolved Jul 18 2022
Sub-tasks:

• Unify "Token" interface in Kuromoji and Nori [LUCENE-10497] #11533

Pull requests: #793, #795, #801, #805

[asfimport]

Tomoko Uchida (@mocobeta) (migrated from JIRA)

I looked through the parse() method of JapaneseTokenizer and KoreanTokenizer  (I'm inclined to change the method name to forward(), this is more aligned with the terminology of the algorithm to me). I perhaps could be too optimistic, but they are not so diverged as I first thought - except for the "unknown" word handling: this is inevitably language-specific.

The N-best path part is also language-agnostic, so I'm expecting that we can safely factor it out from JapaneseTokenizer and have the common utility for performing the minimum n-best cost path calculation. Maybe we will have a utility class for the Viterbi search, and possibly a base tokenizer. I'll try to make a draft patch.

 

[asfimport]

Tomoko Uchida (@mocobeta) (migrated from JIRA)

I'm starting this with small steps. I'll try to keep the commits self-contained, and also as small as possible for safety.
#793
#795

Let me know if there is any feedback, thanks!

[asfimport]

Tomoko Uchida (@mocobeta) (migrated from JIRA)

I'm trying to factor out the core algorithm from Japanese/Korean Tokenizers with the above modifications - it is still a very rough patch but anyhow, seems to work...
I'd merge #793 and #795 after waiting for one or two days and then prepare the main PR. The next step can't be small to show the full picture (creating a base Viterbi class in analysis-common, moving the common logic to it, and rewriting Japanese/Korean Tokenizers upon it), though, I will try to sort out the interfaces for review.

[asfimport]

ASF subversion and git services (migrated from JIRA)

Commit 4d2b085 in lucene's branch refs/heads/main from Tomoko Uchida
https://gitbox.apache.org/repos/asf?p=lucene.git;h=4d2b08554a1

LUCENE-10493: add 'backWordPos' array to JapaneseTokenizer.Position (#793)

[asfimport]

ASF subversion and git services (migrated from JIRA)

Commit 9aa8ec9 in lucene's branch refs/heads/main from Tomoko Uchida
https://gitbox.apache.org/repos/asf?p=lucene.git;h=9aa8ec9d06a

LUCENE-10493: Unify TokenInfoFST in kuromoji and nori (#795)

[asfimport]

ASF subversion and git services (migrated from JIRA)

Commit 13630d3 in lucene's branch refs/heads/main from Tomoko Uchida
https://gitbox.apache.org/repos/asf?p=lucene.git;h=13630d361e2

LUCENE-10493: Unify token Type enum in kuromoji and nori (#801)

[asfimport]

Tomoko Uchida (@mocobeta) (migrated from JIRA)

I opened the main PR: #805.
Please see its description for the design specification and the current limitation (those will be deferred to future work).
It's still a draft but is already self-contained and works correctly (for me). Feedback is welcome.

[asfimport]

ASF subversion and git services (migrated from JIRA)

Commit c89f8a7 in lucene's branch refs/heads/main from Tomoko Uchida
https://gitbox.apache.org/repos/asf?p=lucene.git;h=c89f8a7ea1e

LUCENE-10493: factor out Viterbi algorithm and share it between kuromoji and nori (#805)

[asfimport]

ASF subversion and git services (migrated from JIRA)

Commit c28f575 in lucene's branch refs/heads/main from Tomoko Uchida
https://gitbox.apache.org/repos/asf?p=lucene.git;h=c28f575b6db

LUCENE-10493: move n-best logic to analysis-common (#846)