Elamur Research⌕
☰
home / papers / 2001 / Using Suffix Arrays to Compute Term Frequency and Document Frequency for All Substrings in a Corpus

Using Suffix Arrays to Compute Term Frequency and Document Frequency for All Substrings in a Corpus

Paper · 2001 · Mikio Yamamoto and Kenneth W. Church

Summary

Corpus statistics such as term frequency (tf) and document frequency (df) are usually limited to unigrams, bigrams and trigrams, because a corpus of length N contains a quadratic number of substrings. Yamamoto and Church extend these counts to n-grams of any length. They build a suffix array, an alphabetically sorted list of all suffix positions, and group substrings that share identical statistics into equivalence classes, which they call lcp-delimited intervals. Since the number of classes is only linear, obtaining tf and df for all substrings takes O(N log N) time. They ran the method on 50 million words of Wall Street Journal English and 216 million characters of Mainichi Shimbun Japanese. They then compared two measures of departure from chance. Mutual information (MI) tends to surface dictionary-style, noncompositional phrases. Residual IDF (RIDF), which measures deviation from a Poisson spread over documents, tends to surface names, technical terms and good retrieval keywords. In Japanese word extraction, combining the two worked better than either alone. The work makes arbitrary-length n-gram statistics practical for languages with very large alphabets.

Key points

  • The roughly N²/2 substrings collapse into at most 2N − 1 classes, and every member of a class shares the same tf and df.
  • Suffix arrays use far less memory than suffix trees, whose space grows with alphabet size. This matters for Japanese, which has more than 5,000 characters, and for English treated as a word-level alphabet.
  • RIDF is defined as observed IDF minus the IDF predicted by a Poisson model given the term's tf.
  • In Japanese word extraction, judges rated samples of 100 substrings:
    • Substrings high in both MI and RIDF were words 38–55% of the time.
    • Substrings high in RIDF only were words 29–51% of the time, and those high in MI only 20–44%.
    • Substrings low in both were words just 0–8% of the time.
  • The C code (suffix array construction, interval enumeration, df counting) is included in the appendix and released at milab.is.tsukuba.ac.jp/myama/tfdf.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🏢AT&TBedminster · United States40 works · 75,466 citations🎓University of TsukubaTsukuba · Japan4 works · 945 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 works

💡 Concepts 1Key ideas and methods explained on our concept pages.TF-IDF · 26 works

Cite

Cite as Mikio Yamamoto and Kenneth W. Church. 2001. Using Suffix Arrays to Compute Term Frequency and Document Frequency for All Substrings in a Corpus. Computational Linguistics.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.1162/089120101300346787

@article{yamamoto2001using,
  title = {{Using Suffix Arrays to Compute Term Frequency and Document Frequency for All Substrings in a Corpus}},
  author = {Mikio Yamamoto and Kenneth W. Church},
  journal = {Computational Linguistics},
  year = {2001},
  doi = {10.1162/089120101300346787},
  url = {https://doi.org/10.1162/089120101300346787}
}

References

17 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Charniak, Eugene. 1993. Statistical Language Learning. MIT Press. find
  2. Church, Kenneth W. and William A. Gale. 1995. Poisson mixtures. Natural Language Engineering, 1(2):163-190. find
  3. Gonnet, Gaston H., Ricardo A. Baeza-Yates, and Tim Snider. 1992. New indices for text: PAT trees and PAT arrays. In Information Retrieval: Data Structure & Algorithms, pages 66-82. Prentice Hall PTR. find
  4. Gusfield, Dan. 1997. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press. find
  5. Hui, Lucas Chi Kwong. 1992. Color set size problem with applications to string matching. In Lecture Notes in Computer Science, Volume 644. Springer (CPM92: Combinatorial Pattern Matching, 3rd Annual Symposium), pages 230-243. find
  6. Jelinek, Frederick. 1997. Statistical Methods /or Speech Recognition. MIT Press. find
  7. Katz, Slava M. 1987. Estimation of probabilities from sparse data for the language model component of a speech recognizer. IEEE Transactions on Acoustics, Speech, and Signal Processing, ASSP-35(3):400-401. find
  8. Kita, Kenji, Yasuhiko Kato, Takashi Omoto, and Yoneo Yano. 1994. A comparative study of automatic extraction of collocations from corpora: Mutual information vs. cost criteria. Journal of Natural Language Processing, 1(1):21-33. find
  9. Manber, Udi and Gene Myers. 1990. Suffix arrays: A new method for on-line string searches. In Proceedings of The First Annual ACM-SIAM Symposium on Discrete Algorithms, pages 319-327. URL=http://glimpse.cs.arizona.edu/udi.html. find
  10. McCreight, Edward M. 1976. A space-economical suffix tree construction algorithm. Journal of the ACM, 23:262-272. find
  11. Nagao, Makoto and Shinsuke Mori. 1994. A new method of n-gram statistics for large number of n and automatic extraction of words and phrases from large text data of Japanese. In Proceedings of the 15th International Conference on Computational Linguistics, pages 611-615. find
  12. Nagata, Masaaki. 1996. Automatic extraction of new words from Japanese texts using generalized forward-backward search. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, pages 48-59. find
  13. Paul, Douglas B. and Janet M. Baker. 1992. The design for the Wall Street Journal-based CSR corpus. In Proceedings of DARPA Speech and Natural Language Workshop, pages 357-361. find
  14. Shibatani, Masayoshi. 1990. The Languages of Japan. Cambridge Language Surveys. find
  15. Sparck Jones, Karen. 1972. A statistical interpretation of term specificity and its application in retrieval. Journal of Documentation, 28(1):11-21. find
  16. Sproat, Richard and Chilin Shih. 1990. A statistical method for finding word boundaries in Chinese text. Computer Processing of Chinese and Oriental Languages, 4(4):336-351. find
  17. Ukkonen, Esko. 1995. On-line construction of suffix trees. Algorithmica, 14(3):249-260. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/yamamoto-2001-suffix-arrays-compute-term-frequency/