Advanced search
Publication Cover
International Journal of Computer Mathematics Volume 79, 2002 - Issue 6
Submit an article Journal homepage
30
Views
2
CrossRef citations to date
0
Altmetric
Original Articles

An Efficient Trie Construction for Natural Language Dictionaries

T. Sumitomo Dept. of Information Science and Intelligent Systems, The University of Tokushima, Minami-Josanjima-Cho, Tokushima City, 770-8506, Japan
,
K. Morita Dept. of Information Science and Intelligent Systems, The University of Tokushima, Minami-Josanjima-Cho, Tokushima City, 770-8506, Japan
,
M. Fuketa Dept. of Information Science and Intelligent Systems, The University of Tokushima, Minami-Josanjima-Cho, Tokushima City, 770-8506, Japan
,
H. Tokunaga Dept. of Information Science and Intelligent Systems, The University of Tokushima, Minami-Josanjima-Cho, Tokushima City, 770-8506, Japan
&
J.-I. Aoe Dept. of Information Science and Intelligent Systems, The University of Tokushima, Minami-Josanjima-Cho, Tokushima City, 770-8506, Japan
Pages 703-713 | Published online: 15 Sep 2010

  • Aho , A. V and Corasick , M. J. 1975 . Efficient string matching: An aid to bibliographic search . Commun. ACM. , 18 (6} ) : 333 – 340 .
  • Aho , A. V , Hopcioft , J. E. and Ullman , J. D. 1983 . Data Structures and Algorithms , 163 – 169 . Reading, Mass. : Addison-Wesley .
  • Aho , A. V , Sethi , R. and Ullman , J. D. 1986 . Compilers Principles, Techniques, and Tools , Reading, Mass. : Addison-Wesley . Ch. 2
  • Ai-Suwaiyel , M. and Horawitz , E. 1984 . “Algorithms for trie compaction,” . ACM Trans. Database Syst. , 9 (2} ) : 243 – 263 .
  • Aoe , J. 1984 . “A method for improving string pattern matching machines,” . IEEE Thou. Software Eng. , SE-10 (1} ) : 116 – 120 .
  • Aoe , J. , Morimoto , K. , Shishibori , M. and Parie , K.-H. 1996 . “A trie compaction method for a large get of keys,” . IEEE Irons. Knowledge and Data , KDE-8 (3} ) : 476 – 491 .
  • Aoe , J. 1988 . “A fast digital search algorithm using a double-anay structure,” . IEICE, J71 , D (9} ) : 1592 – 1600 . (in Japanese} Trans.
  • Aoe , J. 1989 . “An efficient digital search algorithm by using a double-anay SbUCtUIe,” . IEEE Trans. Software Eng. , SE-15 (9} ) : 1066 – 1077 .
  • Aoe , J. 1982 . “A practical method for compressing sparse matrices with invariant entries,” . Int. J. Comput. Math. , 12 (2} ) : 97 – 111 .
  • Aoe , J. , Morimoto , K. and Hase , M. 1992 . “An algorithm of compressing common suffixes for trie structures,” . (in Japanese} Thins. IEICE , J75-D-II (4} )
  • Aoe , J. , Morimoto , K. and Sato , T. 1992 . “An efficient implementation of trie structure,” . Software-Pract. & Expr. , 22 (9} ) : 695 – 721 .
  • Appel , A. W. and Jacobson , G. J. 1988 . “The woildt fastest scrabble program,” . Commun. ACM , 31 (5} ) : 572 – 578 .
  • Blumer , A. , Blumer , J. , Haussler , D. and Mcconnel , R. 1987 . “Complete inverted files for efficient text retrieval and analysis,” . J. Assoc. Comput. Mack. , 34 (3} ) : 578 – 595 .
  • Lucchesi , C. L. and Knowaltowski , T. 1993 . “Applications of finite automata representing large vocabularies,” . Software-pract. & Exper. , 23 (1} ) : 15 – 30 .
  • Dundas , J. A. 1991 . “Implementing dynamic minimal-prefix tries,” . Software-pract. & Exper. , 21 (10} ) : 1027 – 1040 .
  • Enbody , R. J. and Du , H. C. 1988 . “Dynamic hashing schemes,” . ACM Computing Surveys , 20 (20} ) : 85 – 113 .
  • Fagin , R. , Nieveigelt , J. , Pippenger , N. and Strong , H. R. 1979 . “Extensible hashing-A fast access method for dynamic files,” . ACM Trans. DatabaseSyst. , 4 (9} ) : 315 – 344 .
  • Fredkin , E. 1960 . “Trie memory,” . Commun. ACM. , 3 (9} ) : 490 – 500 .
  • Fredman , M. L. , Komlos , J. and Szemeredi , E. 1984 . “Storing a sparse table with O(1}worst case access time,” . J. ACM. , 31 (3} ) : 538 – 544 .
  • Jonge , W. D. , Tanenbaum , A. S. and Reit , R. P. 1987 . “Two access methods using compact binary trees,” . IEEE Trans. Software Eng. , SE-13 (7} ) : 799 – 810 .
  • Knuth , D. E. 1973 . The Art of Computer Programming , vol. 3 , 481 – 505 . Sorting and Searching .
  • Litwin , W. A. , Roussopolulos , N. , Levy , G. and Hong , W. 1991 . “Trie hashing with controlled load,” . IEEETrans. Software. Eng. , SE-17 (7} ) : 678 – 691 .
  • Maty , K. 1976 . “Compressed tries,” . Commun. ACM. , 19 (7} ) : 409 – 415 .
  • Matsukawa , T. , Nakamura , J. and Nagao , M. 1989 . “An algorithm of word clustering from co-occurrence data usingDM decomposition and statical estimation,” . Research report; Information Processing Society ofJapan . (in Japanese}
  • Morimoto , K. and Aoe , J. “A method for building morphological and co-occunence dictionaries by triestructures,” , Research report; Information Processing Society of Japan . (in Japanese}
  • Nagao , M. , Tuji , J. , Yamagami , A. and Tatebe , S. 1978 . “Data-structure of a large Japanese dictionary andmorphological analysis by using it,” . Journal of Information Processing Society of Japan , 19 (6} ) : 514 – 521 . (in Japanese}
  • Nakajima , A. and Sugimura , R. 1989 . "Japanese morphological analyzer with TRIE structure dictionary and graphstack for local ambiguity packing,” . 39th Natl. Conf. on Information processing Society of Japan . 1989 . Vol. 1F4 , (in Japanese}
  • Peterson , J. L. 1980 . Computer Programs for Spelling Correction , Lecture Notes in Comput Sci. New York : Springer-Verlag .
  • Procter , P. , ed. 1984 . Longman Dictionary of Contemporary English , Longman Group Ltd. .
  • Standish , T. A. 1980 . Data Structure Techniques , Reading, Mass. : Addison-Wesley . Ch. 3
  • Tarjan , R. E. and Yao , A. C. 1979 . “Storing a sparse table,” . Commun. ACM. , 22 (11} ) : 606 – 611 .

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Order Reprints Request Corporate Permissions

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

Request Academic Permissions

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.

Related research

People also read lists articles that other readers of this article have read.

Recommended articles lists articles that we recommend and is powered by our AI driven recommendation engine.

Cited by lists all citing articles based on Crossref citations.
Articles with the Crossref icon will open in a new tab.