Некоторые методы анализа распределений Q-граммов в задачах классификации данных и приближенного поиска по шаблону
Диссертация
Как отмечалось выше, существенный выигрыш при использовании предложенного метода достигается при поиске достаточно больших шаблонов. Однако крупные шаблоны относительно редко встречаются на практике. Теоретически предложенный метод позволяет осуществлять поиск разрывного шаблона, либо нескольких шаблонов за один сеанс поиска, требующий линейного от размера данных времени. Это свойство… Читать ещё >
Список литературы
- Abrahamson K., Generalized string matching, SI AM Journal on Computing, 16(6), 1039−1051, 1987.
- Aho A.V., Algorithms for finding patterns in strings, Chapter 5 (pp. 255 300) of Leeuwen J. van (ed.) Handbook of Theoretical Computer Science, Elsevier Science Publishers, Amsterdam.
- Altschul, S.F., Gish, W., Miller, W., Myers, E.W. & Lipman, D.J. (1990) «Basic local alignment search tool.» J. Mol. Biol. 215:403−410
- Amir A., Landau G.M., and Vishkin U., Efficient pattern matching with scaling, Journal of Algorithms, 13(1), 2−32, 1992.
- Ankerst M., G. Kastenmuller, H.-P. Kriegel, and T. Seidl, Nearest neighbor classification in 3D protein databases. In Proc. ISMB, 1999.
- Aoe J., Computer Algorithms String Pattern Matching Strategies, IEEE Computer Society Press, Los Alamitos, California, 1994.
- Baeza-Yates R., and Gonnet G.H., A new approach to text searching, Communications of the ACM, 35(10), 74−82, 1992.
- Baeza-Yates R., Improved string matching, Software-Practice and Experience, 19(3), 257−271, 1989
- Baeza-Yates R.A., Algorithms for String Searching: A Survey, ACM SIGIR Forum, 23(3−4), 34−58, 1989.
- Basic Local Alignment Search Tool (NCBI). http://www.ncbi.nlm.nih.gov/BLAST
- Blumer A., Blumer J., Haussler D., Ehrenfeucht A., Chen M.T., and Seiferas J., The smallest automaton recognizing the subwords of a text, Theoretical Computer Science, 40(1), 31−55, 1985.
- Boyer R.S., and Moore J.S., A fast string searching algorithm, Communications of the ACM, 20(10), 762−772, 1977.
- Britten, R.J., Divergence between samples of chimpanzee and human DNA sequences is 5%, counting indels. Proc. Natl. Acad. Sci. USA 99: 13 633−16 335
- S. Burkhardt, A. Crauser, P. Ferragina, H. P. Lenhof, and M. Vingron. q-gram based database searching using a suffix array (QUASAR). In Int. Conf. RECOMB, Lyon, April 1999.
- Campbell R. J. and P. J. Flynn, A survey of free-form object representation and recognition techniques. Computer Vision and Image Understanding, 81:166 210, 2001
- Chang W, Marr T., Approximate string matching and local similarity, In Proc Combinatorial Pattern Matching 94, 259−273, Springer-Verlag, 1994.
- Charras C., and Lecroq T., Exact string matching algorithms, Technical Report, 1997.
- Chen D.-Y., M. Ouhyoung, X.-P. Tian, and Y.-T. Shen, On visual similarity based 3D model retrieval. Computer Graphics Forum, pages 223−232, 2003.
- Colussi L., Fatest pattern matching in strings, Journal of Algorithms, 16(2), 163−189, 1994
- Crochemore M., and Rytter W., Text Algorithms, Oxford University Press, 1994.
- Elad M., A. Tal, and S. Ar, Content based retrieval of VRML objects an iterative and interactive approach. In 6th Eurographics Workshop on Multimedia 2001.
- Galil Z., Giancarlo R., Improved string matching with k mismatches, Sigact News, 17,52−54, 1986.
- GenBank. http://www.nebi.nlm.nih.gov/Genbank/index.html
- Gheorghiciuc I., PhD Thesis, UNIVERSITY OF PENNSYLVANIA. 2004. The subword complexity of finite and infinite binary words.
- Gribskov M., J. Devereux, Sequence Analysis Primer. Stockton Press, 1991.
- Hall P., Dowling G., Approximate string matching, ACM Computing Surveys, 12(4), 381−402, 1980
- Haralick R. M., K. Shanmugam, I. Dinstein, Textural features for image classification // IEEE Transactions on SMC 1973. SMC-3(6) P. 610−621.
- Hetzel G., B. Leibe, P. Levi, and B. Schiele, 3D object recognition from range images using local feature histograms. International Conference on Computer Vision and Pattern Recognition, December 2001.
- Horn B., Extended Gaussian images. Proc. of the IEEE, 72(12): 1671−1686, December 1984
- Hume A., and Sunday D., Fast string searching, Software-Practice and Experience, 21 (11), 1221 -1248, 1991.
- Ivanko E., Perevalov D. On Using Sign Method For 3D Images Recognition And Classification // International Conference on Computing, Communications and Control Technologies: CCCT'04, Austin, Texas USA. 2004. Volume V, P.248−251
- Ivanko E., D. Perevalov., Q-Gram Statistics Descriptor in 3D Shape Classification. Proceedings of Third International Conference on Advances in Pattern Recognition. LNCS 3686−3687, Part II, pp. 360−367, August 2005
- Ivanko E., Perevalov D., Wilson B. Provisional Patent Application 60/585 738, USA, 2004.
- Jain A., P. Duin, and J. Mao, «Statistical pattern recognition: A review». IEEE Transactions on PAMI 22(1), pp. 4−37, 2000.
- Janson S., S. Lonardi, and W. Szpankowski. On average sequence complexity. Theoretical Computer Science, 326(1—3):213—227, 2004
- Jarvelin K. and J. Kekalainen, IR evaluation methods for retrieving highly relevant documents. In 23rd Annual International ACMSIGIR Conference on Research and Development in Information Retrieval, 2000.
- Kang S. and K. Ikeuchi, Determining 3-D object pose using the complex extended Gaussian image. In CVPR, pages 580−585, June 1991.
- Kaufman L. and P. J. Rousseeuw, Finding Groups in Data: An Introduction to Cluster Analysis. John Wiley & Sons, Inc. (1990).
- Kazhdan M., T. Funkhouser, and S. Rusinkiewicz, Rotation invariant spherical harmonic representation of 3D shape descriptors. In Symposium on Geometry Processing, June 2003.
- Knuth D.E., Morris J.H., and Pratt V.R., Fast pattern matching in strings, SIAM Journal on Computing, 6(2), 323−350, 1977.
- Kurtz S., Approximate string searching under weighted edit distance, in Proc. WSP 96, 156−170, Carleton University Press, 1996.
- Landau G.M., Vishkin U., Efficient String Matching with k Mismatches, Theoretical Computer Science, 43, 239−249, 1986
- Landau G.M., Vishkin U., Fast String Matching with k Differences, Journal of Computer and System Sciences, 37, 63−78, 1988.
- Leifman G., S. Katz, A. Tal, and R. Meir. Signatures of 3D models for retrieval, pages 159−163, February 2003.
- Liu Z., Du X., and Ishii N., An improved adaptive string searching algorithm, Software-Practice and Experience, 28(2), 191−198, 1998.
- Lopresti D., A. Tomkins, Block Edit Models for Approximate String Matching, Theoretical Computer Science, vol. 181, 1997, pp. 159−179
- Manber U., «A text compression scheme that allows fast searching directly in the compressed file,» technical report 93−07, Department of Computer Science, University of Arizona (March 1993).
- Manolopoulos Y., and Faloutsos C., Experimenting with pattern matching algorithms, Information Sciences, 90(1−4), 75−89, 1996.
- Mark J., Orr L., Introduction to Radial Basis Function Networks. Centre for Cognitive Science, University of Edinburgh
- McCreight E., A space-economical suffix tree construction algorithm, Journal of the ACM, 23(2), 262−272, 1976.
- Misener Ed.S., S.A.Krawetz, Bioinformatics Methods and Protocols (Methods in molecular biology, vl32), 513c
- Navarro G., A guided tour to approximate string matching. Technical Report TR/DCC-99−5, Dept. of Computer Science, Univ. of Chile, 1999
- Osada R., T. Funkhouser, B. Chazelle, and D. Dobkin, Matching 3D models with shape distributions. Shape Modeling International, pages 154−166, May 2001
- Princeton Shape Benchmark (2004), http://shape.cs.princeton.edu/benchmark
- Rijsbergen C. K., Information Retrieval. Butterworths, 1975
- Saupe D. and D. V. Vranic, 3D model retrieval with spherical harmonics and moments. In B. Radig and S. Florczyk, editors, DAGM 2001, pages 392−397, September 2001
- Schiele B. and J. L. Crowley, Recognition without correspondence using multidimensional receptive field histograms. International Journal of Computer Vision, 36(1):31−52, 2000.
- Smit G. De V., A Comparison of Three String Matching Algorithms, Software-Practice and Experience, 12(1), 57−66, 1982.
- Stephen G.A., : String Searching Algorithms book. Lecture Notes Series on Computing Vol. 3, World Scientific Publishing Co., Singapore 1994
- Sutinen E., Tarhio J., On using q-gram locations in approximate string matching, In Proc ESA 95, 327−340, Springer-Verlag, 1995.
- Taxonomy browser. http://www.ncbi.nlm.nih.gov/Taxonomy/
- Ukkonen E., Approximate string matching with q-grams and maximal matches, Theoretical Computer Science, 1, 191−211, 1992.
- Vandeborre J.-P., V. Couillet, and M. Daoudi, A practical aproach for 3D model indexing by combining local and global invariants. 3D Data Processing Visualization Transmission (3DPVT02), pages 644−647, June 2002.
- Vranic D. V., An improvement of rotation invariant 3D shape descriptor based on functions on concentric spheres. In IEEE International Conference on Image Processing (ICIP 2003), volume 3, pages 757−760, September 2003
- Welch T.A., A technique for high performance data compression / IEEE Computer 17(6):8−19, June 1984
- Wu S., and Manber U., Fast text searching allowing errors, Communications of the ACM, 35(10), 83−91, 1992.
- Yamada H., K. Yamamoto, K. Hosokawa, Directional mathematical morphology reformalized Hough Transformation for the analysis of topographic maps // IEEE Transactions on PAMI 1993 Vol. PAMI-15, N.4. P. 380−387.
- Zaharia T. and F. Preteux, 3D shape-based retrieval within the MPEG-7 framework. In SPIE Conf. on Nonlinear Image Processing and Pattern Analysis XII, volume 4304, pages 133−145, January 2001
- Анисимов Б.В., Курганов В., Распознавание и цифровая обработка изображений. М.1983
- Гнеденко Б. В., А. Я. Хинчин., Элементарное введение в теорию вероятностей. Едиториал УРСС, 2003 г.
- Горбань А.Н., Россиев Д. А., Нейронные сети на персональном компьютере. Н.1996
- Гренадер У., Лекции по теории образов: В 3 тт. Анализ образов (кн.2) М. 1981
- Дуда Р., Харт П., Распознавание образов и анализ сцен. М. Мир, 1976.
- Загорулько Ю.А., Методы представления и обработки знаний: Семантические сети и системы продукций. Методическое пособие. Изд-во НГУ. Новосибирск, 1996
- Иванко Е.Е., «Бессмысленные компьютеры остались в прошлом» / Научно-популярный журнал «Универсум». Москва. 2004 № 5 С.27
- Иванко Е.Е., Об одном методе поиска по шаблону на топографических картах. Вычислительные технологии. Новосибирск. 2005 г. Т. 10 № 3 С.39−46.
- Иванко Е.Е., Шемякин Д. А., Система картографирования и мониторинга сети./Телематика'2004/Сборник трудов всероссийской конференции. Санкт-Петербург. 2004 г. С. 102−103
- Кнут Д., Искусство программирования. Т. 1 3. М., СПб., Киев: ИД «Вильяме», 2000.
- Колмогоров А.Н., Теория информации и теория алгоритмов. М.: Наука, 1987.303 с.
- Кормен Т., Лейзерсон Ч., Ривест Р., Алгоритмы, построение и анализ. М.: МЦНМО, 2000.
- Котов В.Е., Сабельфельд В. К., Теория схем программ. М.: Наука, 1991.
- Краснощеков П.С., Петров A.A., Принципы построения моделей. М.: Фазис, 2002.
- Кузин Л.Т., Основы кибернетики, т.2. Основы кибернетических моделей. М. 1979
- Кузин Л.Т., Синтаксическое распознавание образов (лингвистические модели распознавания). Основы кибернетики, т.2. сс. 173−185
- Левенштейн В.И., Двоичные коды с исправлением выпадений и вставок символа 1, Пробл. перед, информ., 1,1, 1965, 12−25
- Нефедов Е. И., Т. И. Субботина, А. А. Яшин., Современная биоинформатика. -М.:ГОРЯЧАЯ ЛИНИЯ ТЕЛЕКОМ, 272 С., 2005.
- Ope О., Теория графов. М.: Наука, 1980.
- Перевалов Д., Иванко Е., Использование ассоциативных семантических сетей для классификации звукозаписей. Статьи, принятые к публикации на сайте международной конференции Диалог-2004.http://www.dialog21 .ru/Archi ve/2004/Perevalov.htm
- Подиновский В.В., Ногин В. Д., Парето-оптимальные решения многокритериальных задач. М.: Наука, 1981.
- Поляк Б.Т., Введение в оптимизацию. М.: Наука, 1984.
- Поспелов Д. А., Логико-лингвистические модели в системах управления. Москва, Энергоиздат, 1981
- Поспелов Д.А., Моделирование рассуждений. Опыт анализа мыслительных актов Москва, Радио и связь, 1989
- Рубашкин В.Ш., Представление и анализ смысла в интеллектуальных информационных системах. М.: Наука, 1989
- Сэведж Дж. Э., Сложность вычислений. М.: Факториал, 1998.
- Ту Дж., Гонсалес Р., Принципы распознавания образов. М. 1978.- 413с.
- Фаллер Д.М., Молекулярная биология клетки. Руководство для врачей. Изд-во Бином. 272 С.
- Форсайт Д. А., Понс Ж., Компьютерное зрение. Современный подход.: Пер. с англ. М.: Издательский дом «Вильяме», 2004.
- Хмелёв Д.В., Распознавание автора текста с использованием цепей A.A. Маркова / Вестник МГУ, сер.9: Филология, N02, 2000, с. 115−126
- Чень Ч., Ли Р., Математическая логика и автоматическое доказательство теорем. М.1983.- 360с.
- Яблонский C.B., Введение в дискретную математику. М.: Наука, 2001.