Владимир Иосифович Левенштейн

Владимир Иосифович Левенштейн

Дата рождения

20 мая 1935 года

Место рождения

Москва, СССР

учёный

Владимир Иосифович Левенштейн — советский и российский математик, доктор физико-математических наук, ведущий научный сотрудник Института прикладной математики имени М.В. Келдыша, автор алгоритма оценки схожести строк.

Научная карьера

Владимир Левенштейн родился 20 мая 1935 года.

В 1958 году окончил механико-математический факультет Московского государственного университета имени М.В. Ломоносова.

С тех пор работает в Институте прикладной математики имени М.В. Келдыша.

В 1965 году при изучении последовательностей $0-1$ ввёл понятие дистанции редактирования, названное «Расстояние Левенштейна».

Расстояние Левенштейна (также функция Левенштейна) в теории информатики и компьютерной лингвистики является мерой разницы двух последовательностей символов (строк) относительно минимального количества операций вставки, удаления и замены, необходимых для перевода одной последовательности в другую.

Пример:

Чтоб перевести слово «конь» в слово «кот» необходимо совершить одно удаление и одну замену, соответственно дистанция Левенштейна составляет 2:

1. Конь
2. Коть (Заменяем н на т)
3. Кот (Удаляем ь)

Другой пример: имеется два слова, необходимо преобразовать одно слово в другое, используя только удаление, добавление и замену:

1. Машка Миша — исходное состояние
2. Мишка Миша — шаг 1 (замена)
3. Миша Миша — шаг 2 (удаление)

Вывод: расстояние Левенштейна от строки Машка до строки Миша равно 2.

Практическим применением дистанции Левенштейна является определение похожести последовательностей символов, например, при проверке правописания или поиске дубликатов.

Программисты на PHP имеют функцию levenshtein, которая вычисляет дистанцию Левенштейна.

В 2006 году Левенштейн получил медаль Ричарда Хэмминга.

Исследования посвящены оптимизационным комбинаторым задачам кодирования и тестирования, универсальным границам для кодов и дизайнов и теория ортогональных многочленов, синхронизационным свойствам последовательностей, кодов и автоматов, а также изучению совершенных кодов, исправляющих одиночные ошибки различных типов.

Труды

• В.И.Левенштейн, Об одном классе систематических кодов, Докл. АН СССР, 131, 5, 1960, 1011-1014.
• В.И.Левенштейн, Применение матриц Адамара к одной задаче теории кодирования, Проблемы кибернетики, вып. 5, ГИФМЛ, Москва, 1961, 125-136.
• В.И.Левенштейн, О некоторых свойствах кодовых систем, Докл. АН СССР, 140, 6, 1961, 1274-1277.
• В.И.Левенштейн, Самонастраивающиеся автоматы для декодирования сообщений, Докл. АН СССР, 141, 6, 1961, 1320-1323.
• В.И.Левенштейн, Об обращении конечных автоматов, Докл. АН СССР, 147, 6, 1962, 1300-1303.
• В.И.Левенштейн, Об устойчивом доопределении конечных автоматов, Проблемы кибернетики, вып. 10, ГИФМЛ, Москва, 1963, 281-286.
• В.И.Левенштейн, О некоторых своствах кодирования и самонастраивающихся автоматах для декодирования сообщений, Проблемы кибернетики, вып. 11, ГИФМЛ, Москва, 1964, 63-121.
• В.И.Левенштейн, Декодирующие автоматы, инвариантные относительно начального состояния, Проблемы кибернетики, вып. 12, ГИФМЛ, Москва, 1964, 125-136.
• В.И.Левенштейн, Двоичные коды с исправлением выпадений, вставок и замещений символов, Докл. АН СССР, 163, 4, 1965, 845-848.
• В.И.Левенштейн, Двоичные коды с исправлением выпадений и вставок символа 1, Пробл. перед. информ., 1, 1, 1965, 12-25.
• В.И.Левенштейн, Об одном методе решения задачи синхронизации цепи автоматов за минимальное время, Пробл. перед. информ., 1, 4, 1965, 20-32.
• В.И.Левенштейн, Двоичные коды, обеспечивающие синхронизацию и исправление ошибок, Тезисы кратких научных сообщений Международного конгресса математиков, Секция 13, Москва, 1966, 24.
• В.И.Левенштейн, Асимптотически оптимальный двоичный код с исправлением выпадений одного или двух соседних символов, Проблемы кибернетики, вып. 19, Наука, Москва, 1967, 293-298.
• В.И.Левенштейн, Об избыточности и замедлении разделимого кодирования натуральных чисел, Проблемы кибернетики, вып. 20, Наука, Москва, 1968, 173-179.
• В.И.Левенштейн, О синхронизации двусторонних сетей автоматов, Пробл. перед. информ., 4, 4, 1968, 49-62.
• В.И.Левенштейн, Оценки для кодов, обеспечивающих исправление ошибок и синхронизацию, Пробл. перед. информ., 5, 2, 1969, 3-13.
• В.И.Левенштейн, О максимальном числе слов в кодах без перекрытий, Пробл. перед. информ., 6, 4, 1970, 88-90.
• В.И.Левенштейн, Об одном методе построения квазилинейных кодов, обеспечивающих синхронизацию и исправление ошибок, Пробл. перед. информ., 7, 3, 1971, 30-40.
• В.И.Левенштейн, О верхних оценках для кодов с фиксированным весом векторов, Пробл. перед. информ., 7, 4, 1971, 3-12.
• В.И.Левенштейн, О минимальной избыточности двоичных кодов, исправляющих ошибки, Пробл. перед. информ., 10, 2, 1974, 26-42.
• В.И.Левенштейн, Элементы теории кодирования, В кн. Дискретная математика и математические вопросы кибернетики, Наука, Москва, 1974, 207-305.
• В.И.Левенштейн, О максимальной плотности заполнения n-мерного евклидова пространства равными шарами, Математические заметки, 18, 2, 1974, 301-311.
• V.I. Levenshtein, Methods for obtaining bounds in metric problems of coding theory, Proc. of the 1975 IEEE-USSR Joint Workshop on Information Theory, New York, 1976, 126-143.
• В.И.Левенштейн, О границах вероятности необнаружения ошибки, Пробл. перед. информ., 13, 1, 1977, 3-18.
• Г.А. Кабатянский, В.И.Левенштейн, О границах для упаковок на сфере и в пространстве, Пробл. перед. информ., 14, 1, 1978, 3-25.
• В.И.Левенштейн, О выборе многочленов для получения границ в задачах упаковки, VII Всесоюзная конференция по теории кодирования и передачи информации, ч. II, Москва - Вильнюс, 1978, 103-108.
• В.И.Левенштейн, О границах для упаковок в n-мерном евклидовом пространстве, Докл. АН СССР, 245, 6, 1979, 1299-1303.
• В.И.Левенштейн, Границы максимальной мощности кода с ограниченным модулем скалярного произведения, Докл. АН СССР, 263, 6, 1982, 1303-1308.
• В.И.Левенштейн, Границы для упаковок метрических пространств и некоторые их приложения, Проблемы кибернетики, вып. 40, Наука, Москва, 1983, 43-110.
• V.I. Levenshtein, Packing of polynomial metric spaces, Third International Workshop on Information Theory, Convolutional codes; multi-user communication, Sochi, 1987, 271-274.
• В.И.Левенштейн, О прямолинейной границе для экспоненты вероятности необнаруженной ошибки, Пробл. перед. информ., 25, 1, 1989, 33-37.
• V.I. Levenshtein, Perfect deletion-correcting codes as combinatorial designs, Proc. of the Second International Workshop: Algebraic and Combinatorial Coding Theory, Leningrad, USSR, 1990, 137-140.
• В.И.Левенштейн, О совершенных кодах в метрике вставок и выпадений, Дискретная математика, 3, 1, 1991, 3-20.
• V.I. Levenshtein, Designs as maximum codes in polynomial metric spaces, Acta Applicandae Mathematicae, vol.29 (1992), 1-82.
• V.I. Levenshtein, Bounds for self-complementary codes and their applications, in Eurocode-92. CISM Courses and Lectures, vol. 339. Springer-Verlag, Wien-New-York, 1993, 159-171.
• V.I. Levenshtein, Bounds for codes as solutions of extremum problems for systems of orthogonal polynomials, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Lectures Notes in Computer Science, vol. 673, Springer-Verlag, 1993, 25-42.
• V.I. Levenshtein and A.J.H. Vinck, Perfect (d,k)-codes capable of correcting single peak-shifts, IEEE Trans. Inform. Theory, vol. 39, no. 2 (1993), 656-662.
• V.I. Levenshtein, Packing and decomposition problems for polynomial association schemes, Europ. J. Combinatorics, vol. 14 (1993), 461-477.
• T. Ericson and V.I. Levenshtein, Superimposed codes in the Hamming space, IEEE Trans. Inform. Theory, vol. 40, no. 6 (1994), 1882-1893.
• G. Fasekas and V.I. Levenshtein, On upper bounds for code distance and covering radius of designs in polynomial metric spaces, J. Combin. Th. Ser. A, vol. 70, no. 2 (1995), 267-288.
• T. Helleseth, T.Klove, V.I. Levenshtein, and O.Ytrehus, Bounds on the minimum support weights, IEEE Trans. Inform. Theory, vol. 41, no. 2 (1995), 432-440.
• V.I. Levenshtein, Krawtchouk polynomials and universal bounds for codes and designs in Hamming spaces, IEEE Trans. Inform. Theory, vol. 41, no. 5 (1995), 1303-1321.
• В.И.Левенштейн, Простое доказательство основных неравенств для фундаментальных параметров кодов в полиномиальных схемах отношений, Пробл. перед. информ., 31, 4, 1995, 37-50.
• V.I. Levenshtein, Reconstructing binary sequences by the minimum number of their subsequences or supersequences of a given length. Proceedings of Fifth Intern. Workshop on Algebr. and Combin. Coding Theory, Sozopol, Bulgaria, June 1-7, 1996, 176-183.
• V.I. Levenshtein, Lower bounds on crosscorrelation of codes. Proceedings of IEEE Fourth Intern. Symp. on Spread Spectrum Techniques and Appl., Mainz, Germany, September 22-25, 1996, 657-661.
• V.I. Levenshtein, Split orthogonal arrays and maximum independent resilient systems of functions, Designs, Codes and Cryptography, vol. 12, no. 2 (1997), 131-160.
• T.Helleseth, T.Klove, and V.I. Levenshtein, On the information function of an error-correcting code, IEEE Trans. Inform. Theory, vol. 43, no. 2 (1997), pp. 549-557.
• В.И.Левенштейн, Восстановление обьектов по минимальному числу искаженных образцов, Доклады Российской Академии наук, 354, 5, 1997, 593-596.
• P. Delsarte and V.I. Levenshtein, Association schemes and coding theory, IEEE Trans. Inform. Theory, vol. 44, no. 6 (1998), 2477-2504.
• V.I. Levenshtein, Universal bounds for codes and designs, in Handbook of Coding Theory, V.S. Pless and W.C. Huffman, Eds., Amsterdam: Elsevier, vol. 1, 499-648, 1998.
• V.I. Levenshtein, On designs in compact metric spaces and a universal bound on their size, Discrete Mathematics, vol. 192 (1998), 251-271.
• V.I. Levenshtein, On the maximum T-wise independent systems of Boolean functions, Workshop on Coding and Cryptography, Paris, France, 1999, 367-370.
• V.I. Levenshtein, Equivalence of Delsarte's bounds for codes and designs in symmetric association schemes and some applications, Discrete Mathematics, vol. 197/198 (1999), 515-536.
• V.I. Levenshtein, New lower bounds on aperiodic crosscorrelation of binary codes, IEEE Trans. Inform. Theory, vol. 45, no. 1 (1999), 284-288.
• В.И. Левенштейн, О дизайнах в непрерывных единичных кубах, Труды IV Международной конференции: Дискретные модели в теории управляющих систем, МГУ, МАКС Пресс, 2000, 62-64.
• V.I. Levenshtein, Efficient reconstruction of sequences, IEEE Trans. Inform. Theory, vol. 47, no. 1 (2001), 2-22.
• V.I. Levenshtein, Efficient reconstruction of sequences from their subsequences or supersequences, Journal of Combin. Theory, Ser. A, vol. 93, no. 2 (2001), 310-332.
• T. Berger and V.I. Levenshtein, Asymptotical efficiency of two-stage testing, IEEE Trans. Inform. Theory, vol. 48, no. 7 (2002), 1741-1749.
• T. Berger and V.I. Levenshtein, Application of cover-free codes and combinatorial designs to two-stage testing, Discrete Applied Mathematics.
• T.Helleseth, T.Klove and V.I. Levenshtein, Hypercubic 4 and 5-designs from double-error-correcting BCH codes, Designs, Codes and Cryptography.
• V.I. Levenshtein, A universal bound for a covering in regular posets and its application to pool testing, Discrete Mathematics.
• T.Helleseth, T.Klove and V.I. Levenshtein, Error-correction capability of binary linear codes and the discrete simplex problem, IEEE Trans. Inform. Theory.
• V.I. Levenshtein, Combinatorial problems motivated by comma-free codes, Discrete Mathematics.