Wypełnione komórki
Odległość edycyjna
Zachowane litery

  • Wypełniana
  • Odczytywana
  • Odpowiedź

Więcej o odległości edycyjnej

Odległość edycyjna (odległość Levenshteina)

Ile zmian pojedynczych liter zamienia kitten w sitting? Trzy: zamień k na s, zamień e na i i dodaj g. Ta liczba to odległość edycyjna. Dzięki niej programy do sprawdzania pisowni układają podpowiedzi, a biolodzy porównują geny. Wpisz dwa słowa i zobacz, jak tabela ją znajduje. Naciśnij Odtwórz, aby zobaczyć, jak wypełnia się tabela, albo użyj przycisków Krok i Wstecz, aby iść krok po kroku. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce. Wpisz dwa słowa: pierwsze biegnie wzdłuż lewego boku tabeli, drugie wzdłuż górnej krawędzi. Każda komórka zawiera najmniejszą liczbę operacji, które zamieniają litery do jej wiersza w litery do jej kolumny. Na końcu operacje są odczytywane wstecz od prawej dolnej komórki. Nowy przykład wybiera inną parę słów. Gdy plansza jest zaznaczona, strzałki przesuwają o krok, spacja odtwarza i wstrzymuje, a Home i End przeskakują na początek i na koniec.

Jak to działa

  1. Wpisz dwa słowa: pierwsze biegnie wzdłuż lewego boku tabeli, drugie wzdłuż górnej krawędzi.
  2. Naciśnij Odtwórz albo użyj przycisków Krok i Wstecz, aby iść krok po kroku. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce.
  3. Zobacz, jak każda komórka bierze najtańszego z trzech sąsiadów, a potem jak operacje są odczytywane wstecz na pomarańczowo.

Jak działa tabela

Komórka zawiera najmniejszą liczbę operacji, które zamieniają litery pierwszego słowa do jej wiersza w litery drugiego słowa do jej kolumny. Pierwszy wiersz liczy wstawienia, które budują drugie słowo od zera, a pierwsza kolumna liczy usunięcia. Jeśli dwie litery komórki są równe, kopiuje ona lewą górną komórkę: żadna operacja nie jest potrzebna. W przeciwnym razie jest o jeden większa od najmniejszego z trzech sąsiadów: lewego górnego dla zamiany, górnego dla usunięcia i lewego dla wstawienia.

Odczytywanie operacji wstecz

Prawa dolna komórka to odległość edycyjna. Zaczynając od niej, aplikacja sprawdza, od którego sąsiada pochodzi wartość komórki, i przechodzi do niego: po przekątnej dla litery zachowanej lub zamienionej, w górę dla usuniętej, w lewo dla wstawionej. Czytane od lewego górnego rogu kroki tworzą najkrótszą listę operacji, pokazaną pod tabelą: zwykła litera jest zachowana, k→s to zamiana, −e usunięcie, a +g wstawienie.

Często zadawane pytania

Czym jest odległość Levenshteina?

To inna nazwa tej odległości edycyjnej: najmniejsza liczba wstawień, usunięć i zamian pojedynczych liter, które zmieniają jeden napis w drugi. Jej nazwa pochodzi od nazwiska twórcy: Vladimir Levenshtein opisał ją w 1965 roku.

Jaka jest odległość edycyjna między kitten a sitting?

3: zamień k na s, zamień e na i i wstaw g na końcu. Tabela pokazuje, że nie istnieje krótsza lista operacji.

Jak szybki jest algorytm odległości edycyjnej?

Dla słów o długościach m i n tabela ma (m + 1)·(n + 1) komórek, a każda jest wypełniana w jednym kroku, więc zajmuje to czas O(m·n). Jeśli potrzebna jest tylko sama odległość, wystarczą dwa wiersze tabeli.

Jakie są inne odległości edycyjne?

Odległość Damerau–Levenshteina liczy też zamianę miejscami dwóch sąsiednich liter jako jedną operację, co pasuje do literówek. Odległość Hamminga dopuszcza tylko zamiany i działa dla napisów tej samej długości. Odległość LCS dopuszcza tylko wstawienia i usunięcia.

Czy cokolwiek jest gdzieś wysyłane?

Nie. Wszystko jest obliczane w Twojej przeglądarce, a ostatnie ustawienia zostają w pamięci lokalnej tej przeglądarki.

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Przejdź do edytora