Celule completate
Distanța de editare
Litere păstrate

  • Se completează
  • Citită
  • Răspuns

Mai multe despre distanța de editare

Distanța de editare (distanța Levenshtein)

Câte modificări de o singură literă transformă kitten în sitting? Trei: înlocuiți k cu s, înlocuiți e cu i și adăugați un g. Acest număr este distanța de editare: așa își ordonează corectoarele ortografice sugestiile și așa compară biologii genele. Scrieți două cuvinte și urmăriți cum o găsește un tabel. Apăsați Redare pentru a urmări cum se completează tabelul sau folosiți Pas și Înapoi pentru a avansa câte un pas. Trageți glisorul pentru pași pentru a sări oriunde. Scrieți două cuvinte: primul este așezat de-a lungul laturii din stânga a tabelului, al doilea de-a lungul marginii de sus. Fiecare celulă conține cel mai mic număr de operații care transformă literele până la rândul ei în literele până la coloana ei. La final, operațiile sunt citite înapoi pornind de la celula din dreapta jos. Exemplu nou alege o altă pereche de cuvinte. Cu tabla selectată, tastele săgeți avansează pas cu pas, bara de spațiu pornește și oprește redarea, iar Home și End sar la început și la sfârșit.

Cum funcționează

  1. Scrieți două cuvinte: primul este așezat de-a lungul laturii din stânga a tabelului, al doilea de-a lungul marginii de sus.
  2. Apăsați Redare sau folosiți Pas și Înapoi pentru a avansa câte un pas. Trageți glisorul pentru pași pentru a sări oriunde.
  3. Urmăriți cum fiecare celulă ia cel mai ieftin dintre cei trei vecini ai săi, apoi cum operațiile sunt citite înapoi cu portocaliu.

Cum funcționează tabelul

O celulă conține cel mai mic număr de operații care transformă literele primului cuvânt până la rândul ei în literele celui de-al doilea cuvânt până la coloana ei. Primul rând numără inserări, care construiesc al doilea cuvânt pornind de la nimic, iar prima coloană numără ștergeri. Dacă cele două litere ale unei celule sunt egale, ea copiază celula din stânga sus: nu e nevoie de nicio operație. Altfel, este cu unu mai mare decât cel mai mic dintre trei vecini: stânga sus pentru o înlocuire, deasupra pentru o ștergere și la stânga pentru o inserare.

Citirea înapoi a operațiilor

Celula din dreapta jos este distanța de editare. Pornind de acolo, aplicația află din care vecin provine valoarea celulei și trece la el: pe diagonală pentru o literă păstrată sau înlocuită, în sus pentru una ștearsă, la stânga pentru una inserată. Citiți din stânga sus, pașii formează o listă de operații cât mai scurtă, afișată sub tabel: o literă simplă este păstrată, k→s este o înlocuire, −e o ștergere și +g o inserare.

Întrebări frecvente

Ce este distanța Levenshtein?

Este un alt nume pentru această distanță de editare: cel mai mic număr de inserări, ștergeri și înlocuiri de câte o literă care transformă un șir în altul. Poartă numele lui Vladimir Levenshtein, care a descris-o în 1965.

Care este distanța de editare dintre kitten și sitting?

3: înlocuiți k cu s, înlocuiți e cu i și inserați g la sfârșit. Tabelul arată că nu există o listă de operații mai scurtă.

Cât de rapid este algoritmul pentru distanța de editare?

Pentru cuvinte de lungimi m și n, tabelul are (m + 1)·(n + 1) celule, fiecare completată într-un pas, deci durează un timp O(m·n). Dacă e nevoie doar de distanță, ajung două rânduri ale tabelului.

Ce alte distanțe de editare mai există?

Distanța Damerau–Levenshtein socotește și interschimbarea a două litere vecine drept o singură operație, ceea ce se potrivește greșelilor de tastare. Distanța Hamming permite doar înlocuiri și funcționează pentru șiruri de aceeași lungime. Distanța LCS permite doar inserări și ștergeri.

Se trimite ceva undeva?

Nu. Totul se calculează în browserul dumneavoastră, iar ultimele setări rămân în spațiul de stocare local al acestui browser.

Ești gata să încerci?

Deschide PictorX în browser – fără instalare și fără card de credit.

Mergi la editor