Edytuj odległość listy za pomocą unikalnych elementów

Odległość edycji Levenshtein-Distance między listami jest dobrze zbadanym problemem. Ale nie mogę znaleźć wiele możliwych ulepszeń, jeśli wiadomo, że żaden element nie występuje więcej niż raz na każdej liście .

Załóżmy również, że elementy są porównywalne / sortowalne (ale listy do porównania nie są sortowane na początek).

$O(\min(m,n)s)$ $O(\min(s,m,n)s)$ $s$

Bardziej formalnie,

jak skutecznie możemy obliczyć odległość edycji między dwoma podanymi ciągami z obietnicą, że nie mają powtarzających się liter? $s,t \in \Sigma^*$

$\Sigma$ to bardzo duży alfabet.

— użytkownik362178
źródło

Jakie jest teraz twoje pytanie; jak przyspieszyć edycję parami lub jak przyspieszyć obliczanie wszystkich par par odległości ciągów znaków?

— Raphael

Podejrzewam, że pytanie brzmi: jak obliczyć odległość edycji między , gdzie to ciągi znaków nad bardzo dużym alfabetem , i gwarantujemy, że żadna litera nie pojawi się dwa razy w lub in (OP reprezentuje każdy ciąg jako listę liter, tj. listę elementów). Ale to wymaga potwierdzenia.

s, t

$s,t$

s, t \in Σ^{*}

$s,t \in \Sigma^*$

Σ

$\Sigma$

s

$s$

t

$t$

— DW

Tak, w tym przypadku duży alfabet składa się z indeksów bazy danych, a „ciągi”, s i t, są listami zawierającymi te indeksy.

— user362178

Dla tych, którzy zastanawiają się nad złożonością: i to długości ciągów wejściowych, a to rzeczywista odległość edycji, więc jest uwzględniona w złożoności. Koszt każdej edycji jest uważany za 1, ale to chyba bez znaczenia przy obliczaniu tego dystansu (ilość edycje ).

m

$m$

n

$n$

s

$s$

s

$s$

— Albert Hendriks

TL; DR: Nieco bardziej restrykcyjny rodzaj odległości edycji, w którym możemy wstawiać i usuwać tylko pojedyncze znaki, można obliczyć w czasie liniowo-rytmicznym, gdy oba (lub tylko jeden) ciąg mają unikatowe znaki. Daje to użyteczne górne i dolne granice odległości edycji Levenshteina.

Wstaw / usuń odległość edycji i najdłuższe wspólne podciągi

Odległość edycji Levenshteina pozwala na wstawianie, usuwanie i podstawianie pojedynczych znaków, przypisując każdemu koszt 1. Jeśli ograniczymy się tylko do wstawiania i usuwania, otrzymamy podobny pomiar odległości, który powoduje, że zastąpienie ma koszt 2 (ponieważ dowolne podstawienie może naśladować za pomocą wstawiania i usuwania). Nie znam standardowej nazwy dla tego bardziej restrykcyjnego rodzaju odległości edytowania, więc nazwiemy ją „wstaw / usuń odległość edycji”. Odpowiada ona ściśle do najdłuższy wspólny podciąg (LCS) Problem , w którym podane są dwa ciągi o długości i , odpowiednio, i chcą wiedzieć, długość najdłuższego podciągu, który pojawia się w obu. Jeśli dwa ciągi mają LCS $m$ $n$ $L$ , następnie mają wstawioną / usuniętą odległość edycji $n+m-2L$ : najłatwiej to sprawdzić, wyrównując ciągi znaków, tak aby znaki w LCS były ułożone jeden na drugim, podczas gdy znaki spoza LCS były wyświetlane naprzeciwko -odstępu postać. Będzie wtedy oczywiste, że możemy edytować pierwszy ciąg znaków w drugim, wstawiając je w dowolnym miejscu -w górnym rzędzie, a usuwając w dowolnym miejscu -w dolnym rzędzie. Na przykład:

-C-IRC-LE
T-RI-CKLE

Tutaj LCS z CIRCLEa TRICKLE, ICLEma długość 4, i odległość zmiana jest rzeczywiście . $6+7-2*4=5$

Najdłużej rosnące podsekwencje

Powodem tego objazdu jest to, że istnieje bardzo skuteczny sposób obliczenia LCS (a tym samym wstawienia / usunięcia odległości edycji), gdy co najmniej jedna z sekwencji zawiera tylko odrębne znaki: W tym przypadku problem LCS można przekształcić w problem znalezienia najdłuższego rosnącego podsekwencji , który można rozwiązać w czasie . Załóżmy, że otrzymaliśmy dwa ciągi i , a ciąg ma różne znaki. Możemy zmienić nazwę pierwszego znaku z na 1, drugiego na 2 i tak dalej, śledząc, jaki numer przypisaliśmy do każdego znaku w tabeli. Następnie w $O(n \log n)$ $A$ $B$ $A$ $A$ $B$ , zmieniamy nazwy jego znaków przy użyciu tej tabeli (tj. każde wystąpienie tego, co było pierwszym znakiem, Azmienia się na 1 itd.). Wreszcie szukamy najdłużej rosnącego podsekwencji w B. Odpowiada to LCS pomiędzy Ai B, i stamtąd możemy natychmiast obliczyć odległość edycji wstawiania / usuwania. Całkowity potrzebny czas to tylko jeśli i mają odpowiednio długości i . $O(n + m\log m)$ $A$ $B$ $n$ $m$

Granice na odległości edycji Levenshteina

Odległość wstawiania / usuwania wyraźnie stanowi górną granicę odległości Levenshteina (ponieważ każda poprawna sekwencja operacji edycji pod odległością wstawiania / usuwania jest również prawidłową sekwencją operacji edycji Levenshteina). Dzielenie odległości edycji wstawiania / usuwania przez 2 daje również dolną granicę, ponieważ w najgorszym przypadku dowolną operację edycji Levenshteina można zmienić na 2 operacje edycji wstawiania / usuwania.

Uogólnienia

Już w 1977 roku Hunt i Szymański opracowali algorytm, który można postrzegać jako uogólnienie najdłuższego rosnącego algorytmu podsekwencji. Jest skuteczny, gdy liczba par pasujących pozycji znaków między dwoma łańcuchami jest niewielka. Jeśli istnieje takich par, ich algorytm zajmuje czas . (Zauważ, że jeśli wszystkie znaki w jednym ciągu są różne.) Ten algorytm był podstawą oryginalnego programu, który traktował całe wiersze tekstu jako pojedyncze znaki. później przeszedł na używanie algorytmu Myersa , gdzie $r$ $O((r + n)\log n)$ $r \le n$ diffdiff $O(nd)$ $d$ to odległość edycji wstawiania / usuwania, ponieważ działa to lepiej, gdy ogólne różnice są małe, ale często pojawiają się niektóre „znaki” (wiersze tekstu) (takie jak wiersz zawierający tylko nawias otwierający w kodzie programu C).

Hunt, J .; Szymanski, T. (1977), „Szybki algorytm do obliczania najdłuższych wspólnych podsekwencji”, Communications of the ACM, 20 (5): 350–353, doi: 10.1145 / 359581.359603

— j_random_hacker
źródło