Моделирование задачи оптимального выравнивания последовательностей
Автор: Знаменский Сергей Витальевич
Журнал: Программные системы: теория и приложения @programmnye-sistemy
Рубрика: Математические основы программирования
Статья в выпуске: 4 (22) т.5, 2014 года.
Бесплатный доступ
Выравнивание последовательностей широко используется в различных компьютерных системах для анализа и оценки близости данных, выделения изменений и родственных задач. Интуитивные требования к постановке задачи оптимального выравнивания последовательностей формализованы в приводимых тестах. Тесты показали, что ни один из широко используемых подходов к близости и выравниванию не соответствует этим требованиям. Описана новая модель минимизации конфликтов при слиянии изменений. Модель приводит к простой постановке задачи оптимального выравнивания последовательностей, удовлетворяющей рассмотренным требованиям.
Метрика левенштейна, непрерывная интеграция., расстояние редактирования, выравнивание последовательностей, сходство строк, разработка по
Короткий адрес: https://sciup.org/14335996
IDR: 14335996
Список литературы Моделирование задачи оптимального выравнивания последовательностей
- Baudiˇ P., Current concepts in version control systems, 2014, arXiv: s 1405.3496.
- Hunt J. W., McIlroy M. D., An algorithm for differential file comparison, Bell Laboratories, 1976, 7 pp.
- Mackall M., “Towards a Better SCM: Revlog and Mercurial”, Proceedings of Linux Symposium. v. 2 (July 19-22, 2006, Ottawa, Ontario, Canada), 2006, pp. 83-90, URL http://mercurial.selenic.com/wiki/Presentations?action=AttachFile amp;do=get amp;target=ols-mercurial-paper.pdf.
- Левенштейн В. И., «Двоичные коды с исправлением выпадений и вставок символа 1», Пробл. передачи информ., 1:1 (1965), c. 12-25.
- MacDonald J., Versioned file archiving, compression and distribution, U.C. Berkeley, 1998, URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi= 10.1.1.38.9429.
- Wieling M., Bloem J., Mignella K., Timmermeister M., Nerbonne J., “Measuring foreign accent strength in English. Validating Levenshtein Distance as a Measure”, The Mind Research Repository (beta), 2013, no. 1, URL http://openscience.uni-leipzig.de/index.php/mr2/article/view/41/30.
- Wu X., Wu Zh., Jia J., Meng H., Cai L., Li W., “Automatic speech data clustering with human perception based weighted distance”, The 9th International Symposium on Chinese Spoken Language Processing, ISCSLP 2014 (12-14 September 2014, Singapore), IEEE, pp. 216-220.
- Luo L., Ming J., Wu D., Liu P., Zhu S., “Semantics-based obfuscation-resilient binary code similarity comparison with applications to software plagiarism detection”, Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering, FSE 2014 (November 16-21, 2014, Hong Kong, China), ACM, 2014, pp. 389-400, URL http://faculty.ist.psu.edu/wu/papers/cop-fse2014.pdf.
- Rho S., Hwang E., “FMF: Query adaptive melody retrieval system”, Journal of Systems and Software, 79:1 (2006), pp. 43-56.
- Durbin R., Eddy S., Krogh A., Mitchison G., Biological sequence analysis: probabilistic models of proteins and nucleic acids, Cambridge University Press, 1998, 356 pp.
- Dohrn H., Riehle D., “Fine-grained change detection in structured text documents”, Proceedings of the 2014 ACM symposium on Document engineering, DocEng 2014 (September 16-19, 2014, Denver, Colorado, USA), ACM, 2014, pp. 87-96.
- Oita M., Senellart P., “Deriving dynamics of web pages: A survey”, TWAW 2011: Temporal Workshop on Web Archiving (March 28, 2011, Hyderabad, India), 2011, URL http://pierre.senellart.com/publications/oita2011deriving.pdf.
- Hall P. A. V., Dowling G. R., “Approximate string matching”, ACM computing surveys, 12:4 (1980), pp. 381-402.
- Diamantopoulos T., Symeonidis A., “Localizing Software Bugs using the Edit Distance of Call Traces”, International Journal on Advances in Software, 7:1-2 (2014), pp. 277-288.
