Rank Distance with Applications in Similarity of Natural Languages

• Autorzy: Dinu L. P.
• Języki publikacji: EN

Abstrakty

EN

In this paper we introduce a metric for measuring the similarity between two classifications which differ by their constitutive elements. Our measure is inspired from natural language and genomics where the most important information is carried by the first part of the unit. We extend the measure to words and to rooted (un)labelled general trees. We use this metric to analyze the syllabic similarity of Romance languages.

Słowa kluczowe

EN

rank distance; similarities; tree-to-tree distance; computing with words; classification; similarity of Romance languages

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2005
• Tom: Vol. 64, nr 1-4
• Strony: 135--149
• Opis fizyczny: Bibliogr. 25 poz., tab., wykr.

Twórcy

autor

Dinu L. P.

• Faculty of Mathematics, Bucharest University, Str. Academiei 14, sector 1, 70109 Bucharest, Romania,

Bibliografia

• [1] P. Bile. Tree edit distance, alignment distance and inclusion. TR-2003-23, ISSN 1600-6100, University of Copenhagen, 2003.
• [2] M. Borelli, A. Sgarro.A possibilistic distance for sequences of equal and unequal length. In Finite VS Infinite: Contributions to an Eternal Dilemma, C. Calude and Gh. P˘aun eds., Springer-Verlag, London, 2000
• [3] L.P. Dinu. Rank distance in mathematical linguistics. Annals of Bucharest Univ., Computer Science Series, 52, 1 (2003), 67–73.
• [4] M. Dinu. Comunicarea (in Romanian). Ed. Ştiinţifică, Bucureşti, 1997.
• [5] R. Fagin, R. Kurnar, M. Mahdian, D. Sivakumar, E. Vee. Comparing and aggregating rankings with ties. In 2004 ACM Symposium on Principles of database systems (PODS 2004), to appear.
• [6] T. Fujisaki, F. Jelinek, J. Cocke, E. Black, T. Nishino. Probabilistic parsing methods for sentence disambiguation. In Proceedings of the International Parsing TechnologiesWorkshop. Carnegie-Mellon Univ., Pittsburgh, 1989.
• [7] R.W. Hamming. Error detecting and error correcting codes. Bell System Technical Journal, 29 (1950), 146–160.
• [8] G. Herdan. The Advanced Theory of Language as Choice and Chance, Springer, New York, 1966
• [9] T. Jiang, L. Wang, K. Zhang. Alignment of trees – an alternative to tree edit. Theoretical Computer Science, 143 (1995), 137–148.
• [10] R. Karp. Mathematical challenges from genomics and molecular biology. Notices of the AMS, 49 (2002), 544–553.
• [11] D.E. Knuth. The Art of Computer Programming vol.1, Reading, Massasuchetts, 1969; vol. 3, AddisonWesley Longman, USA, 1973.
• [12] V. Levenshtein. Binary codes capable of corecting deletions, insertions and reversal. Doklady Akademii Nauk SSSR, 163, 4 (1965), 845–848; also Soviet Physics Doklady, 1018 (1966), 707–710.
• [13] C. Manning, H. Sch¨utze. Foundations of Statistical Natural Language Processing, MIT Press, 1999.
• [14] S. Marcus, Le genre grammatical et son mod`ele logique. Cahiers Ling. Theor. Appl., 1 (1962), 103–123.
• [15] S. Marcus, E. Nicolau, S. Stati. Introduzione alle linguistica matematica. Casa editrice Riccardo Patron, Bologna, 1971.
• [16] S. Marcus. Linguistic structures and generative devices in molecular genetics. Cahiers Ling. Theor. Appl., 11 (1974), 77–104.
• [17] S. Marcus. An emergent triangle: semiotics-genomics-computation. In Proceedings of the Congress of the German Semiotic Society, Kassel, July 2002.
• [18] D.F. Robinson, L.R. Foulds. Comparison of Phylogenetic Trees, Mathematical Biosciences, 53 (1981), 131–147.
• [19] M. Sala (coordinator). Vocabularul reprezentativ al limbilor romanice, Bucureşti, 1982.
• [20] A. Sgarro. A fuzzy Hamming distance, Bull. Math. de la Soc. Sci. Math de la Roumanie, 21(69), 1-2 (1977).
• [21] E. Tanaka. A metric between unrooted and unordered trees and its bottom-up computing method. IEEE Transactions on Pattern Analysis and Machine Intelligence, 16, 12, (1994), 1233–1238.
• [22] J.T.L. Wang, K. Zhang. Finding similar consensus between trees: an algorithm and a distance hierarchy. Pattern Recognition, 34 (2001), 127–137.
• [23] L.A. Zadeh. The concept of a linguistic variable and its application to approximate reasoning. Information Sciences, 8 (1975) 199–249(I), 301–357(II).
• [24] L.A. Zadeh, J. Kacprzyk. Computing with Words in Information/Intelligent Systems 1: Foundations, 2: Application. Physica-Verlag, Heidelberg and New York, 1999.
• [25] A. Ziegler. Word Length in Romance Languages. A Complemental Contribution. Journal of Quantitative Linguistics, 7, 1 (2000), 65–68.