Concept

Levenshtein distance

In information theory, linguistics, and computer science, the Levenshtein distance is a string metric for measuring the difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-character edits (insertions, deletions or substitutions) required to change one word into the other. It is named after the Soviet mathematician Vladimir Levenshtein, who considered this distance in 1965. Levenshtein distance may also be referred to as edit distance, although that term may also denote a larger family of distance metrics known collectively as edit distance. It is closely related to pairwise string alignments. The Levenshtein distance between two strings (of length and respectively) is given by where where the of some string is a string of all but the first character of , and is the th character of the string , counting from 0. Note that the first element in the minimum corresponds to deletion (from to ), the second to insertion and the third to replacement. This definition corresponds directly to the naive recursive implementation. For example, the Levenshtein distance between "kitten" and "sitting" is 3, since the following 3 edits change one into the other, and there is no way to do it with fewer than 3 edits: kitten → sitten (substitution of "s" for "k"), sitten → sittin (substitution of "i" for "e"), sittin → sitting (insertion of "g" at the end). The Levenshtein distance has several simple upper and lower bounds. These include: It is at least the absolute value of the difference of the sizes of the two strings. It is at most the length of the longer string. It is zero if and only if the strings are equal. If the strings have the same size, the Hamming distance is an upper bound on the Levenshtein distance. The Hamming distance is the number of positions at which the corresponding symbols in the two strings are different. The Levenshtein distance between two strings is no greater than the sum of their Levenshtein distances from a third string (triangle inequality).

Official source

https://en.wikipedia.org/wiki/Levenshtein_distance

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related courses (32)

PHYS-100: Advanced physics I (mechanics)

La Physique Générale I (avancée) couvre la mécanique du point et du solide indéformable. Apprendre la mécanique, c'est apprendre à mettre sous forme mathématique un phénomène physique, en modélisant la situation et appliquant les lois de la physique. ...

CS-421: Machine learning for behavioral data

Computer environments such as educational games, interactive simulations, and web services provide large amounts of data, which can be analyzed and serve as a basis for adaptation. This course will cover the core methods of user modeling and personalizatio ...

MATH-111(c): Linear Algebra

L'objectif du cours est d'introduire les notions de base de l'algèbre linéaire et ses applications. ...

Related lectures (32)

Distances and Motif Counts

Explores distances on graphs, cut norms, spanning trees, blockmodels, metrics, norms, and ERGMs in network data analysis.

Graph metrics: Statistical analysis

Explores graph metrics and statistical analysis in network clustering, including ERGMs application in sociology and asymptotics.

Error-Correcting Codes: Hamming Distance and Polynomial Multiplication

Covers error-correcting codes, Hamming distance, and polynomial multiplication in algebraic fields.

Related units (2)

Security and Cryptography Laboratory

SNAI - Administration

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Official source

https://en.wikipedia.org/wiki/Levenshtein_distance

About this result

Related courses (32)

PHYS-100: Advanced physics I (mechanics)

CS-421: Machine learning for behavioral data

MATH-111(c): Linear Algebra

L'objectif du cours est d'introduire les notions de base de l'algèbre linéaire et ses applications. ...

Related lectures (32)

Distances and Motif Counts

Explores distances on graphs, cut norms, spanning trees, blockmodels, metrics, norms, and ERGMs in network data analysis.

Graph metrics: Statistical analysis

Explores graph metrics and statistical analysis in network clustering, including ERGMs application in sociology and asymptotics.

Error-Correcting Codes: Hamming Distance and Polynomial Multiplication

Covers error-correcting codes, Hamming distance, and polynomial multiplication in algebraic fields.

Related publications (24)

Causal analysis of extreme risk in a network of industry portfolios

We provide a detailed review of causal dependence within the framework of max‐linear structural models. Such models express each node variable as a max‐linear function of its parental node variables in a directed acyclic graph (DAG) and some exogenous innovation. We reformulate results on structure learning and estimation, which we apply to a network of financial data. A new method, based on hard‐thresholding and on the Hamming distance, estimates a sparse DAG for extreme risk propagation.

Wiley2026

GeneTEK: Low-power and high-performance FPGA scalable architecture for exact unit-cost edit distance

The advent of next-generation sequencing (NGS) has revolutionized genomic research by enabling cost-effective, high-throughput sequencing of a diverse range of organisms. This breakthrough has unleashed a "Cambrian explosion" in genomic data volume and diversity. This volume of workloads places genomics among the top four big data challenges anticipated for this decade. In this context, pairwise sequence alignment represents a very time- and energy-intensive step in common bioinformatics pipelines. Speeding

Elsevier BV2026

Sensor network localization has a benign landscape after low-dimensional relaxation

We consider the sensor network localization problem, which is closely related to multidimensional scaling and Euclidean distance matrix completion. Given a ground truth configuration of n points in

{\mathbb {R}}^\ell

, we observe a subset of the pairwise distances and aim to recover the underlying configuration (up to rigid transformations). We show with a simple counterexample that the associated optimization problem is nonconvex and may admit spurious local minimizers, even when all distances are known

Springer Science and Business Media LLC2026

Related people (19)

Pascal Frossard

Teaching & PhD PhD Students Yiming Qin, Alba Carballo Castro, Elisa Messori, Ke Wang, Sevda Ögüt, Tuna Alikasifoglu, William Cappelletti, Manuel Madeira, Mahdi Amiri, Ortal Yona Senouf, Vasiliki Rizou, Cem Bilaloglu, Abdellah Rahmani, Amel Abdelraheem, Jérémy Jean Philippe Baffou, Adam Hazimeh, Vincent Jung, Yike Zhao Past EPFL PhD Students Dan Jurca, Jean-Paul Wagner, Ivana Radulovic, Ivana Tosic, Effrosyni Kokiopoulou, Zafer Arican, Vijayaraghavan Thirumalai, Tamara Tosic, Eirina Bourtsoulatze, Elif Vur

Hervé Bourlard

Teaching & PhD Past EPFL PhD Students Astrid Hagen, Katrin Weber, Todd Stephenson, Jitendra Ajmera, Shajith Ikbal, Mathew Magimai Doss, Mohamed Faouzi Benzeghiba, Mark Barnard, Yann Rodriguez, Hemant Misra, Christos Dimitrakakis, Guillaume Lathoud, Alexei Pozdnoukhov, Agnès Just, Mikaela Keller, Norman Hoon Thian Poh, Dong Zhang, Florent Monay Michaud, Pedro Manuel Da Silva Quelhas, Kevin Smith, Silèye Oumar Ba, Bertrand Mesot, Hamed Ketabdar, David Grangier, Guillermo Aradilla, Jean-François Paiement, Nico

Pascal Fua

Pascal Fua received an engineering degree from Ecole Polytechnique, Paris, in 1984 and the Ph.D. degree in Computer Science from the University of Orsay in 1989. He then worked at SRI International and INRIA Sophia-Antipolis as a Computer Scientist. He joined EPFL in 1996 where he is now a Professor in the School of Computer and Communication Science and heads the Computer Vision Laboratory. His research interests include shape modeling and motion recovery from images, analysis of microscopy images, and Augmented Reality. His research interests include shape modeling and motion recovery from images, analysis of microscopy images, and machine learning. He has (co)authored over 300 publications in refereed journals and conferences. He is an IEEE Fellow and has been an Associate Editor of IEEE journal Transactions for Pattern Analysis and Machine Intelligence. He often serves as program committee member, area chair, and program chair of major vision conferences and has cofounded three spinoff companies (Pix4D, PlayfulVision, and NeuralConcept).

Friedrich Eisenbrand

Friedrich Eisenbrand's main research interests lie in the field of discrete optimization, in particular in algorithms and complexity, integer programming, geometry of numbers, and applied optimization. He is best known for his work on efficient algorithms for integer programming in fixed dimension and the theory of cutting planes, which are an important tool to solve large scale industrial optimization problems in practice. Before joining EPFL in March 2008, Friedrich Eisenbrand was a full professor of mathematics at the University of Paderborn. Friedrich received the Heinz Maier-Leibnitz award of the German Research Foundation (DFG) in 2004 and the Otto Hahn medal of the Max Planck Society in 2001.

Martin Vetterli

Martin Vetterli was appointed president of EPFL by the Federal Council following a selection process conducted by the ETH Board, which unanimously nominated him. Professor Vetterli was born on 4 October 1957 in Solothurn and received his elementary and secondary education in Neuchâtel Canton. He earned a Bachelor’s degree in electrical engineering from ETH Zurich (ETHZ) in 1981, a Master’s of Science degree from Stanford University in 1982, and a PhD from EPFL in 1986. Professor Vetterli taught at Columbia University as an assistant and then associate professor. He was subsequently named full professor in the Department of Electrical Engineering and Computer Sciences at the University of California at Berkeley before returning to EPFL as a full professor at the age of 38. He has also taught at ETHZ and Stanford University. Professor Vetterli has earned numerous national and international awards for his research in electrical engineering, computer science and applied mathematics, including the National Latsis Prize in 1996. He is a fellow of both the Association for Computing Machinery and the Institute of Electrical and Electronics Engineers and a member the US National Academy of Engineering. He has published over 170 articles and three reference works. Professor Vetterli’s work on the theory of wavelets, which are used in signal processing, is considered to be of major importance by his peers, and his areas of expertise, including image and video compression and self-organized communication systems, are central to the development of new information technologies. As the founding director of the National Centre of Competence in Research on Mobile Information and Communication Systems, Professor Vetterli is a staunch advocate of transdisciplinary research. Professor Vetterli knows EPFL inside and out. An EPFL graduate himself, he began been teaching at the school in 1995, was vice president for International Affairs and then Institutional Affairs from 2004 to 2011, and served as dean of the School of Computer and Communication Sciences in 2011 and 2012. In addition to his role as president of the National Research Council of the Swiss National Science Foundation, a position he held from 2013 to 2016, he heads the EPFL’s Audiovisual Communications Laboratory (LCAV) since 1995. Professor Vetterli has supported more than 60 students in Switzerland and the United States in their doctoral work and makes a point of following their highly successful careers, whether it is in the academic or business world. He is the author of some 50 patents, some of which were the basis for start-ups coming out of his lab, such as Dartfish and Illusonic, while others were sold (e.g. Qualcomm) as successful examples of technology transfer. He actively encourages young researchers to market the results of their work.

Marco Mattavelli

Teaching & PhD Past EPFL PhD Students Christophe Clerc, Ruohua Zhou, Beilu Shao, Christophe Lucarz, Richard Thavot, Ab Al Hadi Bin Ab Rahman, Endri Bezati, Simone Casale Brunet, Malgorzata Michalska, Ana Angelica Hernandez Lopez, Aurélien Bloch, Mustafa Besirli, Ünsal Öztürk Past EPFL PhD Students as codirector Sylvain Aguirre Courses Systems and architectures for signal processing EE-555 Study of the essential components and implementation technologies of digital signal processing and commu

Michaël Unser

Expertise Image Processing, Medical Imaging, Biological Imaging, Wavelets, Splines, Multiresolution Michael Unser is Full Professor with EPFL’s school of Engineering and the academic director of EPFL's Center for Imaging, Lausanne, Switzerland. His primary areas of investigation are signal processing, biomedical imaging and applied functional analysis. He is internationally recognized for his research contributions to sampling theory, wavelets, the use of splines for image processing, stochastic processes,

Rüdiger Urbanke

Rüdiger L. Urbanke obtained his Dipl. Ing. degree from the Vienna University of Technology, Austria in 1990 and the M.Sc. and PhD degrees in Electrical Engineering from Washington University in St. Louis, MO, in 1992 and 1995, respectively. He held a position at the Mathematics of Communications Department at Bell Labs from 1995 till 1999 before becoming a faculty member at the School of Computer & Communication Sciences (I&C) of EPFL. He is a member of the Information Processing Group. He is principally interested in the analysis and design of iterative coding schemes, which allow reliable transmission close to theoretical limits at low complexities. Such schemes are part of most modern communications standards, including wireless transmission, optical communication and hard disk storage. More broadly, his research focuses on the analysis of graphical models and the application of methods from statistical physics to problems in communications. From 2000-2004 he was an Associate Editor of the IEEE Transactions on Information Theory and he is currently on the board of the series "Foundations and Trends in Communications and Information Theory." In 2017 he was President of the Information Theory Society. From 2009 till 2012 he was the head of the I&C doctoral school, in 2013 he served as Dean a. i. of I&C, and since 2016 he is the Associated Dean for teaching of I&C. He is a co-author of the book "Modern Coding Theory" published by Cambridge University Press. Awards: 2021 IEEE Information Theory Society Paper Award 2016 STOC Best Paper Award 2014 La Polysphere Teaching Award 2014 IEEE Hamming Medal 2013 IEEE Information Theory Society Paper Award 2011 MASCO Best Paper Award 2011 IEEE Koji Kobayashi Award 2009 La Polysphere Teaching Award 2002 IEEE Information Theory Society Paper Award Fulbright Scholarship My students have won the following awards: M. Mondelli, 2021 IEEE Information Theory Paper Award M. Mondelli, EPFL Doctorate Award 2018 M. Mondelli, Patrick Denantes Award, 2017 M. Mondelli, IEEE IT Society Student Paper Award at ISIT, 2015 M. Mondelli, Dan David Prize Scholarship, 2015 H. Hassani, Inaugural Thomas Cover Dissertation Award, 2014 S. Kudekar, 2013 & 2021 IEEE Information Theory Paper Award A. Karbasi, Patrick Denantes Award, 2013 V. Venkatesan, Best Paper Award at MASCOTS, 2011 A. Karbasi, Best Student Paper Award at ICASSP, 2011 (with R. Parhizkar) A. Karbasi, Best Student Paper Award at ACM SIGMETRICS, 2010 (with S. Oh) S. Korada, ABB Dissertation Award, 2010 S. Korada, IEEE IT Society Student Paper Award at ISIT, 2009 (with E. Sasoglu) S. Korada, IEEE IT Society Student Paper Award at ISIT, 2008

Patrick Thiran

Patrick Thiran is a full professor in network and systems theory at the School of Computer and Communication Sciences at EPFL. He holds an electrical engineering degree from the Université Catholique de Louvain, Louvain-la-Neuve, Belgium, an M.Sc. degree in electrical engineering from the University of California at Berkeley, USA, and he received the PhD degree from EPFL, in 1996. He became an adjunct professor in 1998, an assistant professor in 2002, an associate professor in 2006 and a full professor in 2011. He was with Sprint Advanced Technology Labs in Burlingame, California, in 2000-01. His research interests are in communication and social networks, performance analysis and stochastic models. He is currently active in the analysis and design of wireless and PLC networks (scaling laws, medium access control), in network monitoring (network tomography, multi-layer networks), and data-driven network science. He also contributed to network calculus and to the theory of locally coupled neural networks and self-organizing maps. He served as an associate editor for the IEEE Transactions on Circuits and Systems in 1997-99 and for the IEEE/ACM Transactions on Networking in 2006-10. He is currently on the editorial board of the IEEE Journal on Selected Areas in Communication. He is/was on the program committee of different conferences in networking, including ACM Sigcomm, Sigmetrics, IMC, CoNext and IEEE Infocom. He was TPC chair of AMC IMC 2011 and CoNext 2012. He is a Fellow of the Belgian American Educational Foundation and of the IEEE. He received the 1996 EPFL Doctoral Prize and the 2008 Crédit Suisse Teaching Award.

Simon Nessim Henein

Born in 1973 and of Egyptian-Swiss nationality, Simon Henein grew up in Cairo. He obtained an engineering degree at the Ecole Polytechnique Fédérale de Lausanne (EPFL) in 1996 and went on to complete his doctorate at the EPFL in 2000. In 2001, he published the book “Conception des guidages flexibles” which has become a reference in precision engineering. He then joined the Centre Suisse d’Electronique et Microtechnique (CSEM), Neuchatel, Switzerland, where he conceived and developed mechanisms for robotic, aerospace, medical and watchmaking applications. He pursued his research career at the Paul Scherrer Institute, Villigen, Switzerland, where he developed instruments for the Swiss Light Source Synchrotron (SLS). Since November 1st, 2012, he is associate professor in microengineering at the EPFL, holder of the Patek Philippe Chair and director of the Micromechanical and horological design laboratory (Instant-Lab).

Related units (2)

Security and Cryptography Laboratory

SNAI - Administration

Related concepts (5)

Longest common subsequence

A longest common subsequence (LCS) is the longest subsequence common to all sequences in a set of sequences (often just two sequences). It differs from the longest common substring: unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences. The problem of computing longest common subsequences is a classic computer science problem, the basis of data comparison programs such as the diff utility, and has applications in computational linguistics and bioinformatics.

Edit distance

In computational linguistics and computer science, edit distance is a string metric, i.e. a way of quantifying how dissimilar two strings (e.g., words) are to one another, that is measured by counting the minimum number of operations required to transform one string into the other. Edit distances find applications in natural language processing, where automatic spelling correction can determine candidate corrections for a misspelled word by selecting words from a dictionary that have a low distance to the word in question.

String metric

In mathematics and computer science, a string metric (also known as a string similarity metric or string distance function) is a metric that measures distance ("inverse similarity") between two text strings for approximate string matching or comparison and in fuzzy string searching. A requirement for a string metric (e.g. in contrast to string matching) is fulfillment of the triangle inequality. For example, the strings "Sam" and "Samuel" can be considered to be close.

Related exercises (32)

Coupled oscillator

Two material points, with identical mass m, are frictionlessly moving in a straight line, on a horizontal track (see diagram). They are attached together by a spring with constant K. Each material point is attached to a fixed point on the track by another spring, with constant k. The three springs have rest length l₀, and the fixed points are separated by a distance 3l₀.

Write each material point’s equations of motion.
Deduce the equations of motion of the center of mass and that system’s rela

Conceptual questions on moment of inertia

Consider a full bottle. Order the moments of inertia around the four axes shown in the diagram: the bottle’s symmetry axis A, and the three axes perpendicular to A going through, respectively, the bottle’s cork (B), its center of mass (C), and its base (D). Knowing that I₁u2004

Cylinder

A positive charge Q is placed in the centre of a cylinder with radius R and length L at a distance L/4 from the left face, as illustrated in the figure. The flux of the electric field through the cylinder is Φ₀. What is the flux through the cylinder if its length is reduced to L/2 while keeping the left face fixed, as illustrated in the figure. The same charge is enclosed in the smaller cylinder as in the larger cylinder. Thus also the flux is the same:

\Phi_0=\frac{Q}{\epsilon_0}

Related notebooks (5)

Interactive Phonon Band Structure Visualization

In [1]: import numpy as np import matplotlib.pyplot as plt from matplotlib import animation from matplotlib import rc import ipywidgets as ipw from ipywidgets import interact,interactive import ipywidgets as widgets from IPython.display import HTML %matplotlib widget global global_K1 global global_K2 global global_branche global global_selected_k In [2]: def get_closest_point(clic_x,clic_y): # Get the data from the figure ax= plt.gca() # get axis handle acoustic_data = ax.lines[1] op

Digital Simulation of Guitar Feedback in I Feel Fine by The Beatles

I Feel Fine, Digitally[1]¶ This notebook is a little musing inspired by the "internal mechanics" of a very famous audio snippet, namely the guitar sound at the beginning of the song "I Feel Fine", written and recorded by the Beatles in 1964. The historical significance of the record lies in the following claim by John Lennon:

 "I defy anybody to find a record... unless it is some old blues
 record from 1922... that uses feedback that way. So I claim it for
 the Beatles. Before H

Wave Interference

The plotted function is the superimposition of $n$ 2d-sine functions centered in $(0,Y_i)$: $$f(x,y)=\sin\big(p\cdot\sqrt{x^2+(y-Y_i)^2}\big)$$ The parameters that can be changed are: -- $n$ the number of sources (start with 2) -- $d$ the distance between sources -- $p$ the periodicity. Higher periodicity means shorter wavelength. $p =2\pi / \lambda$. Note that in electron microscopy the usual convention is to define the wave vector as $k=1/\lambda$. -- $f$ the field o

Whistle-Activated Keylock System Implementation

Whistling Keylock[1]¶ In this notebook we will implement a simple "whistle-activated" keylock, that is, an access control system where the password is a pre-defined melody. To program the lock, you record your musical passphrase and then, to open the lock, you whistle it back. Although the implementation will be simple and skip most of the fine details that would be necessary to produce a truly robust system, we need to take into account at least the following points: * The syste

Implementing a Fractional Resampler using Local Lagrange Interpolation

FIR Resampling[1]¶

                                      [2]Paolo Prandoni, [3]LCAV, EPFL

In this notebook we will implement a simple fractional resampler that uses local Lagrange interpolation. The resampler can be used to perform any rational sampling rate change (but beware of aliasing when downsampling!) In [1]: import numpy as np import IPython from scipy.io import wavfile Local Lagrange interpolation[4]¶ To perform resampling we will need to compute subsample values and, in