FUNCTION OF DISTANCE BETWEEN THE STRINGS BASED ON PIECEWISE CONSTANT MODEL
Abstract
A piecewise model of a string which allows to define a distance between two strings is proposed. The model can be applied to problems of fuzzy matching and text analysis and the model can be used with cyclic strings.
About the Author
V. A. Prytkov
Белорусский государственный университет информатики и радиоэлектроники
Belarus
Belarus
References
1. Смит У. Методы и алгоритмы вычислений на строках. М., 2006.
2. Gonzalo Navarro // ACM Computing Surveys. 2001. Vol. 33, № 1. P. 31-88.
3. Graham A. Stephen. String Seaching Algorithms, 1994.
4. Гасфилд Д. Строки, деревья и последовательности в алгоритмах. СПб, 2003.
5. Hamming R.W. // The Bell System Technical Journal. 1950. Vol. XXIX, № 2. P.147-160.
6. Federal Standard 1037C, 1996.
7. Левенштейн В.И. // Докл. Академий Наук СССР. 1965. Т. 163, №4. С. 845-848.
8. Masek W.J., Paterson M.S. // Journal of Computer and System Sciences. 1980. Vol. 20, № 1.
9. Ehrenfeucht A., Haussler D. // Discrete Applied Mathematics. 1988. Vol. 20, № 3. P. 191-203.
10. Ukkonen E. Approximate string-matching with q-grams and maximal matches // Theoretical Computer Science 1992. Vol. 92, № 1. P.191-211.
11. Hall P.A.V., Dowling G.R. // Computing Surveys. 1980. Vol. 12, № 4. P. 381-402.
12. Blumer A., Blumer J., Haussler D. et al. // Theoretical Computer Science. 1985. Vol. 40. P. 31-55.
13. Hirschberg D.S. // Journal of the Assoclauon for Computing Machinery. 1977. Vol. 24, № 4. P. 664-675.
14. Кормен Т., Лейзерсон Ч., Ривест Р. и др. Алгоритмы: построение и анализ. М., 2005.
15. Прытков В.А., Барташевич Ю.А., Лукашевич М.М. // Матер. V межд. конф.-форума «Информационные системы и технологии». Минск, 2009. С. 172-175.
Review
For citations:
Prytkov V.A. FUNCTION OF DISTANCE BETWEEN THE STRINGS BASED ON PIECEWISE CONSTANT MODEL. Doklady BGUIR. 2013;(4):22-28. (In Russ.)
Views: 305
Email this article 