---
title: "Using Suffix Arrays to Compute Term Frequency and Document"
description: "They build a suffix array, an alphabetically sorted list of all suffix positions, and group substrings that… 17 references, cited by 22 papers here."
authors: ["Mikio Yamamoto", "Kenneth W. Church"]
year: 2001
venue: "Computational Linguistics"
source: "https://aclanthology.org/J01-1001/"
doi: "10.1162/089120101300346787"
licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)"
licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/yamamoto-2001-suffix-arrays-compute-term-frequency/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/yamamoto-2001-suffix-arrays-compute-term-frequency/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2001](https://md.research.elamur.ai/free/en/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

**Authors:** Mikio Yamamoto and [Kenneth W. Church](https://md.research.elamur.ai/free/en/authors/kenneth-church/) · **Year:** 2001 · **Venue:** [Computational Linguistics](https://md.research.elamur.ai/free/en/venues/cl/) ([Computational Linguistics 2001](https://md.research.elamur.ai/free/en/venues/cl/2001/)) · **Publisher:** [The MIT Press](https://md.research.elamur.ai/free/en/publishers/the-mit-press/) · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/)

**Links:** [Publisher's page](https://aclanthology.org/J01-1001/) · [PDF](https://aclanthology.org/J01-1001.pdf) · [DOI 10.1162/089120101300346787](https://doi.org/10.1162/089120101300346787) · [OpenAlex](https://openalex.org/W2008434289)

**Citations:** 172 citations (OpenAlex, 2026-10-14) · [22](https://md.research.elamur.ai/free/en/papers/yamamoto-2001-suffix-arrays-compute-term-frequency/cited-by/) in our library, of the 149,439 papers whose bibliographies we read

## 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&T](https://md.research.elamur.ai/free/en/companies/at-t/) — Company, Bedminster, United States · 40 works · 75,466 citations
- [University of Tsukuba](https://md.research.elamur.ai/free/en/universities/university-of-tsukuba/) — University, Tsukuba, Japan · 4 works · 945 citations

📚 Shelves (4): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 16,667 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 16,194 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 16,039 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 15,891 works

💡 Concepts (1): [💡 TF-IDF](https://md.research.elamur.ai/free/en/concepts/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.

```bibtex
@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}
}
```

- [← previous Improving Accuracy in word class tagging through the Combination of Machine Learning Systems](https://md.research.elamur.ai/free/en/papers/halteren-2001-improving-accuracy-word-class-tagging/)
- [next → An Algebra for Semantic Construction in Constraint-based Grammars](https://md.research.elamur.ai/free/en/papers/copestake-2001-algebra-semantic-construction-constraint-based/)
- [↑ back to papers of 2001](https://md.research.elamur.ai/free/en/papers/2001/)

## 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](https://scholar.google.com/scholar?q=Charniak%2C+Eugene%2E+1993%2E+Statistical+Language+Learning%2E+MIT+Press%2E)
2. Church, Kenneth W. and William A. Gale. 1995. Poisson mixtures. Natural Language Engineering, 1(2):163-190. [find](https://scholar.google.com/scholar?q=Church%2C+Kenneth+W%2E+and+William+A%2E+Gale%2E+1995%2E+Poisson+mixtures%2E+Natural+Language+Engineering%2C+1%282%29%3A163%2D190%2E)
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](https://scholar.google.com/scholar?q=Gonnet%2C+Gaston+H%2E%2C+Ricardo+A%2E+Baeza%2DYates%2C+and+Tim+Snider%2E+1992%2E+New+indices+for+text%3A+PAT+trees+and+PAT+arrays%2E+In+Information+Retrieval%3A+Data+Structure+%26+Algorithms%2C+pages+66%2D82%2E+Prentice+Hall+PTR%2E)
4. Gusfield, Dan. 1997. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press. [find](https://scholar.google.com/scholar?q=Gusfield%2C+Dan%2E+1997%2E+Algorithms+on+Strings%2C+Trees%2C+and+Sequences%3A+Computer+Science+and+Computational+Biology%2E+Cambridge+University+Press%2E)
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](https://scholar.google.com/scholar?q=Hui%2C+Lucas+Chi+Kwong%2E+1992%2E+Color+set+size+problem+with+applications+to+string+matching%2E+In+Lecture+Notes+in+Computer+Science%2C+Volume+644%2E+Springer+%28CPM92%3A+Combinatorial+Pattern+Matching%2C+3rd+Annual+S)
6. Jelinek, Frederick. 1997. Statistical Methods /or Speech Recognition. MIT Press. [find](https://scholar.google.com/scholar?q=Jelinek%2C+Frederick%2E+1997%2E+Statistical+Methods+%2For+Speech+Recognition%2E+MIT+Press%2E)
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](https://scholar.google.com/scholar?q=Katz%2C+Slava+M%2E+1987%2E+Estimation+of+probabilities+from+sparse+data+for+the+language+model+component+of+a+speech+recognizer%2E+IEEE+Transactions+on+Acoustics%2C+Speech%2C+and+Signal+Processing%2C+ASSP%2D35%283%29%3A400)
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](https://scholar.google.com/scholar?q=Kita%2C+Kenji%2C+Yasuhiko+Kato%2C+Takashi+Omoto%2C+and+Yoneo+Yano%2E+1994%2E+A+comparative+study+of+automatic+extraction+of+collocations+from+corpora%3A+Mutual+information+vs%2E+cost+criteria%2E+Journal+of+Natural+Lang)
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](https://scholar.google.com/scholar?q=Manber%2C+Udi+and+Gene+Myers%2E+1990%2E+Suffix+arrays%3A+A+new+method+for+on%2Dline+string+searches%2E+In+Proceedings+of+The+First+Annual+ACM%2DSIAM+Symposium+on+Discrete+Algorithms%2C+pages+319%2D327%2E+URL%3Dhttp%3A%2F%2Fglimp)
10. McCreight, Edward M. 1976. A space-economical suffix tree construction algorithm. Journal of the ACM, 23:262-272. [find](https://scholar.google.com/scholar?q=McCreight%2C+Edward+M%2E+1976%2E+A+space%2Deconomical+suffix+tree+construction+algorithm%2E+Journal+of+the+ACM%2C+23%3A262%2D272%2E)
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](https://scholar.google.com/scholar?q=Nagao%2C+Makoto+and+Shinsuke+Mori%2E+1994%2E+A+new+method+of+n%2Dgram+statistics+for+large+number+of+n+and+automatic+extraction+of+words+and+phrases+from+large+text+data+of+Japanese%2E+In+Proceedings+of+the+15t)
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](https://scholar.google.com/scholar?q=Nagata%2C+Masaaki%2E+1996%2E+Automatic+extraction+of+new+words+from+Japanese+texts+using+generalized+forward%2Dbackward+search%2E+In+Proceedings+of+the+Conference+on+Empirical+Methods+in+Natural+Language+Proces)
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](https://scholar.google.com/scholar?q=Paul%2C+Douglas+B%2E+and+Janet+M%2E+Baker%2E+1992%2E+The+design+for+the+Wall+Street+Journal%2Dbased+CSR+corpus%2E+In+Proceedings+of+DARPA+Speech+and+Natural+Language+Workshop%2C+pages+357%2D361%2E)
14. Shibatani, Masayoshi. 1990. The Languages of Japan. Cambridge Language Surveys. [find](https://scholar.google.com/scholar?q=Shibatani%2C+Masayoshi%2E+1990%2E+The+Languages+of+Japan%2E+Cambridge+Language+Surveys%2E)
15. Sparck Jones, Karen. 1972. A statistical interpretation of term specificity and its application in retrieval. Journal of Documentation, 28(1):11-21. [find](https://scholar.google.com/scholar?q=Sparck+Jones%2C+Karen%2E+1972%2E+A+statistical+interpretation+of+term+specificity+and+its+application+in+retrieval%2E+Journal+of+Documentation%2C+28%281%29%3A11%2D21%2E)
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](https://scholar.google.com/scholar?q=Sproat%2C+Richard+and+Chilin+Shih%2E+1990%2E+A+statistical+method+for+finding+word+boundaries+in+Chinese+text%2E+Computer+Processing+of+Chinese+and+Oriental+Languages%2C+4%284%29%3A336%2D351%2E)
17. Ukkonen, Esko. 1995. On-line construction of suffix trees. Algorithmica, 14(3):249-260. [find](https://scholar.google.com/scholar?q=Ukkonen%2C+Esko%2E+1995%2E+On%2Dline+construction+of+suffix+trees%2E+Algorithmica%2C+14%283%29%3A249%2D260%2E)

*Updated 29 October 2026*