Pytania otagowane jako edit-distance

2
wydajny algorytm różnicowy dla drzew i odległości Levenshteina
Niedawno przeczytałem to podsumowanie zagadnień związanych z różnicowaniem między drzewami i zainteresowało mnie poznanie najnowocześniejszych rozwiązań tego problemu. Załóżmy również, że między dozwolonymi operacjami edycji jest tradycyjny węzeł dodawania / usuwania, edytuj zawartość, którą dodajesz rozszerzonymi operacjami poddrzewa kopiuj / przenieś, czy to sprawia, że ​​problem (znalezienie optymalnej różnicy) jest …
1
Edytuj odległość w przestrzeni podliniowej
Jaka jest najbardziej znana złożoność obliczenia dokładnej odległości edycji między dwoma ciągami o tej samej długości przy użyciu przestrzeni roboczej, która jest podliniowa w wielkości wejścia? Zakładam, że dane wejściowe są przechowywane w jakimś formacie tylko do odczytu. Czy to wcześniej badany problem? Aby uczynić pytanie nieco bardziej szczegółowym, co …
3
Edytuj odległość między dwiema partycjami
Mam dwie partycje [1…n][1…n][1 \ldots n] i szukam odległości edycji między nimi. W ten sposób chcę znaleźć minimalną liczbę pojedynczych przejść węzła do innej grupy, które są niezbędne do przejścia z partycji A na partycję B. Na przykład odległość od {0 1} {2 3} {4}do {0} {1} {2 3 4}wynosi …
2
Teoretyczne traktowanie różnic, łat i łączenia?
Czy istnieje kategoria łatek, która wygląda mniej więcej tak: Obiekty są ciągami znaków w pewnym alfabecie podstawowym Morfizmy to skrypty edycyjne („diffs” lub „łatki”) między ciągami Interesują mnie następujące pytania: Czy istnieje kategoryczne pojęcie minimalnego skryptu edycji? Może kategoria łatek jest wzbogacona w zestawy PO? Czy łączenie łat jest kategorycznym …
2
Edytuj odległość za pomocą operacji przesuwania
Motywacja: Współautor redaguje manuskrypt i chciałbym zobaczyć jasne podsumowanie edycji. Wszystkie narzędzia podobne do „diff” są zwykle bezużyteczne, jeśli zarówno przenosisz tekst (np. Reorganizując strukturę), jak i edytujesz lokalnie. Czy to naprawdę takie trudne? Definicje: Chciałbym znaleźć minimalną odległość edycji, gdzie dozwolone operacje to: „tanie” operacje: dodaj / zmień / …
2
Złożoność przestrzeni w celu obliczenia optymalnego wyrównania łańcucha dla odległości edycji Levenshteina
Jeśli otrzymamy dwa ciągi o rozmiarze n1n1n_1 i , standardowe obliczanie odległości edycji Levenshteina odbywa się za pomocą algorytmu dynamicznego o złożoności czasowej i złożoności przestrzennej . (Niektóre ulepszenia można wprowadzić w zależności od odległości edycji , ale nie zakładamy, że jest szczególnie mały.) Jeśli interesuje Cię tylko wartość odległości …
2
Złożoność homogenizacji łańcucha
Motywacja : Opracowując narzędzia do wersjonowania danych, zaczęliśmy szukać algorytmów do „różnicowania” dwóch zestawów liczb całkowitych, wymyślając sekwencję przekształceń, które przenoszą jeden zestaw liczb całkowitych na drugi. Udało nam się zredukować ten problem do następującego bardzo naturalnego problemu, który wydaje się mieć połączenia do edycji odległości, grupowania przez zamianę i …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.