田畑さんのコメントへの私信

コードを見ていただいてCanna, FreeWnnに対してAnthy以降の変換エンジンのアーキテクチャががらりと変わってることに気付いていただければ幸いです。

特許周辺では、重要なアルゴリズムは80年代のAIブーム以前に開発されており、AIブームが冷めて以降に応用が発展したというのが現状のようです。自然言語処理の教科書を適当に見ていただければ(内容がわからなかったら、基本的な項目の年代を見てください)読み取れると思います。

CannaとAnthyを読み比べてみています。パトリシア・トライについて調べてみるか、という気になります。：）

まだまだ見始めですから、まだまだ何もいえません。

PATRICIA trieの論文
ACMで調べてみた。ACMは、Digital Libraryですべての論文や学会誌、さらには一般書籍まで読み放題で大変お徳だ。

• ACM Portal: Patricia tries again revisited

これなんか、新しいアルゴリズムらしい。面白そうである。

• ACM Portal: Burst tries: a fast, efficient data structure for string keys

そして、これがたぶん原典になるのでしょうか。

PATRICIA—Practical Algorithm To Retrieve Information Coded in Alphanumeric
Source Journal of the ACM (JACM) archive
Volume 15 , Issue 4 (October 1968) table of contents
Pages: 514 - 534
Year of Publication: 1968
ISSN:0004-5411
Author Donald R. Morrison Sandia Laboratory, Computer Science, Division 5256, Albuquerque, New Mexico
Publisher
ACM Press New York, NY, USA
Additional Information:

ABSTRACT

PATRICIA is an algorithm which provides a flexible means of storing, indexing, and retrieving information in a large file, which is economical of index space and of reindexing time. It does not require rearrangement of text or index as new material is added. It requires a minimum restriction of format of text and of keys; it is extremely flexible in the variety of keys it will respond to. It retrieves information in response to keys furnished by the user with a quantity of computation which has a bound which depends linearly on the length of keys and the number of their proper occurrences and is otherwise independent of the size of the library. It has been implemented in several variations as FORTRAN programs for the CDC-3600, utilizing disk file storage of text. It has been applied to several large information-retrieval problems and will be applied to others.

PATRICIA trieの実装例

• THE CODE PROJECT: Patricia Trie implementation
• THE CODE PROJECT: Patricia Trie Template Class

告白すると、このデータ構造はこれから学ばなければならない。南無。