Cover not available
Part of
Language and Text: Data, models, information and applications
Edited by Adam Pawłowski, Jan Mačutek, Sheila Embleton and George Mikros
[Current Issues in Linguistic Theory 356] 2021
► pp. 37–54

A method for the comparison of general sequences via type-token ratio

| Palacký University
| University of Oxford
| Charles University

This article proposes a new method for analyzing and comparing general linear sequences with the minimum prior knowledge on the sequences needed. Sequence analysis is a broad problem studied by various fields from sociology and computer security to linguistics or biology. The method presented here applies the simplest quantitative linguistic tools in order to achieve methods transparency and easily interpretable results. The results form a vector describing the sequence and allow their clustering, machine learning and simple visualizations by line charts or multidimensional methods as MDS or tSNE. For completeness, artifacts and several formal models are derived to describe methods behavior in both common and extreme cases.

Keywords: sequence analysis, sequence clustering, randomness test, n-gram, type-token relation, type-token ratio, confidence intervals
Article outline
  • 1.Introduction: Sequence analysis and its importance
  • 2.Method: Quantitative linguistics and the most basic methodology
    • Step 1: Normalization of the alphabet
    • Step 2: Length normalization
    • Step 3: Contextual data collection from n-grams
    • Note: Choosing sequence length k and n-gram size bounding
    • Step 4: Quantification of properties
      • Results: TTR vectors
    • Step 5: Interpretation, visualizations, and beyond
  • 3.Visualization methods
    • 3.1Basic line-chart
    • 3.2Classical Multidimensional Scaling (MDS)
    • 3.3t-Distributed Stochastic Neighbor Embedding
  • 4.Models of sequence behavior in our method
    • 4.1Model of truly random sequences
    • 4.2Model of minimal TTR
    • 4.3Model of maximal TTR
  • 5.Method artefacts and specific n intervals
    • 5.1Interval of exhausting vocabulary Q
    • 5.2Interval of vocabulary saturation C
    • 5.3Interval of maximum variance H
  • 6.Comparison to other, similar purpose methods
  • 7.Conclusions
  • References
Published online: 22 December 2021
DOI logo
https://doi.org/10.1075/cilt.356.03mat
References
Blei, David M., Andrew Y. Ng & Michael I. Jordan
2003 Latent Dirichlet allocation. Journal of Machine Learning Research 3 (4–5). 993–1022.Google Scholar
Bolshoy, Alexander, Zeev (Vladimir) Volkovich, Valery Kirzhner & Zeev Barzily
2010 Genome clustering from linguistic models to classification of genetic texts. Berlin: Springer.Google Scholar
Conroy, Matthew M.
2018 A collection of dice problems. [URL] (16 August 2018.)
Cornwell, Benjamin
2015 Social sequence analysis: Methods and applications, (Structural analysis in the social sciences 37). Cambridge: Cambridge University Press. DOI logoGoogle Scholar
d’Imperio, Mary E.
1978 The Voynich manuscript: An elegant enigma. Fort George G. Meade, MD: National Security Agency/Central Security Service.Google Scholar
Gastwirth, Joseph L.
1972 The estimation of the Lorenz curve and Gini index. The Review of Economics and Statistics 54(3). 306–316. DOI logoGoogle Scholar
Govindan, Vidya, Rajat Subhra Chakraborty, Pranesh Santikellur & Aditya Kumar Chaudhary
2018 A hardware Trojan attack on FPGA-based cryptographic key generation: Impact and detection. Journal of Hardware and Systems Security 2. 225–239. DOI logoGoogle Scholar
Haahr, Mads
2018 True random integer generator, RANDOM.ORG: True Random Number Service. Randomness and Integrity Services Ltd.Google Scholar
Hamano, Kenji & Hirosuke Yamamoto
2010 Randomness test based on T-complexity. Communications and Computer Sciences E93-A(7). 1346–1354. DOI logoGoogle Scholar
Hamid, Raffay, Amos Johnson, Samir Batta, Aaron Bobick, Charles Isbell & Graham Coleman
2005 Detection and explanation of anomalous activities: representing activities as bags of event n-grams. IEEE Computer Society Conference on Computer Vision and Pattern Recognition 1. 1031–1038. DOI logoGoogle Scholar
Huffman, David A.
1952 A method for the construction of minimum-redundancy codes. Proceedings of the IRE 40(9). 1098–1101. DOI logoGoogle Scholar
Jain, Ashish & Narendra S. Chaudhari
2015 A new heuristic based on the cuckoo search for cryptanalysis of substitution ciphers. In Sabri Arik, Tingwen Huang, Weng Kin Lai & Qingshan Liu (eds.), Neural Information Processing (Lecture Notes in Computer Science 9490). 206–215. Dordrecht: Springer. DOI logoGoogle Scholar
Lasry, George
2018 A methodology for the cryptanalysis of classical ciphers with search metaheuristics. Kassel: Kassel University Press.Google Scholar
Maaten, Laurens Van Der & Geoffrey Hinton
2008 Visualizing data using t-SNE. Journal of Machine Learning Research 9(9). 2579–2605.Google Scholar
Matlach, Vladimír
2018 Aplikace kvantitativní lingvistiky na analýzu sekvencí. Olomouc: Palacký University Olomouc PhD dissertation. [URL] (5 December 2019.)
Mikros, George & Jan Macutek
(eds.) 2015 Sequences in language and text, Volume 69. Berlin: Walter de Gruyter GmbH & Co KG. DOI logoGoogle Scholar
Mitzenmacher, Michael & Eli Upfal
2005 Probability and computing: Randomized algorithms and probabilistic analysis. Cambridge: Cambridge University Press. DOI logoGoogle Scholar
Pritchard, Jonathan K., Matthew Stephens & Peter Donnelly
2000 Inference of population structure using multilocus genotype data. Genetics 155(2). 945–959. DOI logoGoogle Scholar
Rao, Rajesh P.
2010 Probabilistic analysis of an ancient undeciphered script. Computer 43(4). 76–80. DOI logoGoogle Scholar
Rao, Rajesh P., Nisha Yadav, Mayank N. Vahia, Hrishikesh Joglekar, R. Adhikari & Iravatham Mahadevan
2009 Entropic evidence for linguistic structure in the Indus script. Science 324. 1165. DOI logoGoogle Scholar
Riedel, Marko
2018 Probability of throwing exactly V distinct sides on N sided dice by K rolls. [URL] (20 June 2018.)
Rukhin, Andrew, Juan Soto, James Nechvatal, Miles Smid & Elaine Barker
2001 A statistical test suite for random and pseudorandom number generators for cryptographic applications. Booz-Allen and Hamilton Inc Mclean VA.Google Scholar
Schenkel, Alain, Jun Zhang & Yi-Cheng Zhang
1993 Long range correlations in human writings. Fractals 1(1). 47–55. DOI logoGoogle Scholar
Shannon, Claude E.
1948 A mathematical theory of communication. Bell System Technical Journal 27(3). 623–656. DOI logoGoogle Scholar
Sproat, Richard
2010 Ancient symbols, computational linguistics, and the reviewing practices of the general science journals. Computational Linguistics 36(3). 585–594. DOI logoGoogle Scholar
2014 A statistical comparison of written language and nonlinguistic symbol systems. Language 90(2). 457–481. DOI logoGoogle Scholar
Stuttard, Dafydd & Marcus Pinto
2011 The web application hacker’s handbook: Finding and exploiting security flaws. Indianapolis: Wiley.Google Scholar
Torgerson, Warren S.
1958 Theory and methods of scaling. New York: Wiley.Google Scholar
Ziv, Jacob & Abraham Lempel
1978 Compression of individual sequences via variable-rate coding. IEEE Transactions on Information Theory 24(5). 530–536. DOI logoGoogle Scholar