Odległość edycji (lub Levenshteina) między dwoma łańcuchami to minimalna liczba wstawek, usunięć i podstawień pojedynczych znaków potrzebnych do przekształcenia jednego łańcucha w drugi. Jeżeli oba ciągi mają długość n, dobrze wiadomo, że można to zrobić w czasie O (n ^ 2) przez programowanie dynamiczne. Poniższy kod Python wykonuje te obliczenia dla dwóch łańcuchów s1i s2.

def edit_distance(s1, s2):
    l1 = len(s1)
    l2 = len(s2)

    matrix = [range(l1 + 1)] * (l2 + 1)
    for zz in range(l2 + 1):
      matrix[zz] = range(zz,zz + l1 + 1)
    for zz in range(0,l2):
      for sz in range(0,l1):
        if s1[sz] == s2[zz]:
          matrix[zz+1][sz+1] = min(matrix[zz+1][sz] + 1, matrix[zz][sz+1] + 1, matrix[zz][sz])
        else:
          matrix[zz+1][sz+1] = min(matrix[zz+1][sz] + 1, matrix[zz][sz+1] + 1, matrix[zz][sz] + 1)
    return matrix[l2][l1]

W tym zadaniu musisz być jak najbliżej obliczenia odległości edycji, ale z poważnym ograniczeniem pamięci. Twój kod może zdefiniować jedną tablicę zawierającą 1000 32-bitowych liczb całkowitych i ma to być jedyna tymczasowa pamięć używana w obliczeniach. Wszystkie zmienne i struktury danych muszą być zawarte w tej tablicy. W szczególności nie można zaimplementować powyższego algorytmu, jak w przypadku ciągów o długości 1000, ponieważ wymagałoby to przechowywania co najmniej 1 000 000 liczb. Tam, gdzie twój język nie ma naturalnie 32-bitowych liczb całkowitych (na przykład Python), musisz po prostu upewnić się, że nigdy nie przechowujesz w tablicy liczby większej niż 2 ^ 32-1.

Możesz odczytywać dane przy użyciu dowolnej standardowej biblioteki, którą wybierzesz, bez obawy o ograniczenia pamięci w tej części. Aby konkurs był sprawiedliwy dla głównej części kodu, możesz używać tylko operacji, które są funkcjonalnie równoważne z operacjami w języku programowania C i nie możesz używać żadnych zewnętrznych bibliotek.

Aby być bardziej przejrzystym, pamięć do przechowywania danych wejściowych lub używana przez tłumacza języka, JVM itp. Nie wlicza się do limitu i nie możesz nic zapisywać na dysku. Musisz założyć, że dane wejściowe są tylko do odczytu, gdy znajdują się w pamięci, więc nie możesz ich ponownie użyć, aby uzyskać więcej miejsca do pracy.

Co muszę wdrożyć?

Twój kod powinien zostać odczytany w pliku w następującym formacie. Będzie miał trzy linie. Pierwszy wiersz to prawdziwa odległość edycji. Drugi to ciąg 1, a trzeci to ciąg 2. Przetestuję go z przykładowymi danymi na stronie https://bpaste.net/show/6905001d52e8, gdzie ciągi mają długość 10 000, ale nie powinno się specjalizować dla tych danych. Powinien generować najmniejszą możliwą odległość edycji między dwoma ciągami.

Będziesz także musiał udowodnić, że odległość do edycji faktycznie pochodzi od prawidłowego zestawu zmian. Twój kod powinien mieć przełącznik, który zmienia go w tryb, który może zużywać więcej pamięci (tyle, ile chcesz) i wyświetla operacje edycji, które dają odległość do edycji.

Wynik

Twój wynik będzie (optimal edit distance/divided by the edit distance you find) * 100. Na początek zauważ, że możesz uzyskać wynik, po prostu licząc liczbę niedopasowań między dwoma ciągami.

Możesz używać dowolnego języka, który ci się podoba, który jest swobodnie dostępny i łatwy do zainstalowania w systemie Linux.

Tie break

W przypadku remisu uruchomię twój kod na moim komputerze z systemem Linux i najszybszy kod wygrywa.

C ++, wynik 92,35

Algorytm szacowania: Algorytm znajduje pierwsze miejsce, w którym różnią się dwa ciągi, a następnie wypróbowuje wszystkie możliwe permutacje operacji N (wstawianie, usuwanie, zamiana - pasujące znaki są pomijane bez wykonywania operacji). Wylicza każdy możliwy zestaw operacji na podstawie tego, o ile dalej ten zestaw operacji z powodzeniem dopasowuje dwa łańcuchy, a także na ile powoduje, że długości łańcuchów się zbiegają. Po określeniu zestawu N operacji o najwyższym wyniku, stosowana jest pierwsza operacja w zestawie, odnajdowane jest kolejne niedopasowanie, a proces jest powtarzany aż do osiągnięcia końca łańcucha.

Program wypróbowuje wszystkie wartości N od 1-10 i wybiera poziom, który dał najlepsze wyniki. N = 10 jest na ogół najlepszy teraz, gdy metoda punktacji uwzględnia długość struny. Wyższe wartości N byłyby prawdopodobnie jeszcze lepsze, ale zajmują wykładniczo więcej czasu.

Użycie pamięci: Ponieważ program jest wyłącznie iteracyjny, potrzebuje bardzo mało pamięci. Tylko 19 zmiennych jest używanych do śledzenia stanu programu. Są one ustawiane przez # definicje, aby działać jak zmienne globalne.

Użycie: Program jest używany tak samo jak feersum: pierwszy parametr jest uważany za plik, a wszelkie dodatkowe parametry wskazują, że zmiany powinny być pokazane. Program zawsze drukuje szacunkową odległość edycji i wynik.

Dane wyjściowe z weryfikacji: dane wyjściowe z weryfikacji sformatowano w trzech wierszach:

11011111100101100111100110100 110 0 0000   0 01101
R I          IR     R        D   D D    DDD D     D
01 1111110010 0001110001101000110101000011101011010

Górny rząd to ciąg docelowy, środkowy to operacje, a dolny to edytowany ciąg. Spacje w wierszu operacji wskazują, że znaki są zgodne. „R” oznacza, że ​​łańcuch edycji ma znak w tej pozycji zastąpiony znakiem łańcucha docelowego. „I” oznacza, że ​​w łańcuchu edycji wstawiono znak łańcucha docelowego w tej pozycji. „D” oznacza, że ​​ciąg znaków edycji ma usunięty znak w tej pozycji. Ciągi edycji i docelowe mają spacje wstawiane, gdy drugi ma znak wstawiony lub usunięty, więc są wyrównane.

#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <math.h>
#include <fstream>

int memory[1000];
#define first (*(const char **)&memory[0])
#define second (*(const char **)&memory[1])
#define block_ia memory[2]
#define block_ib memory[3]
#define block_n memory[4]
#define block_op memory[5]
#define block_o memory[6]
#define block_x memory[7]
#define n memory[8]
#define opmax memory[9]
#define best_op memory[10]
#define best_score memory[11]
#define score memory[12]
#define best_counter memory[13]
#define la memory[14]
#define lb memory[15]
#define best memory[16]
#define bestn memory[17]
#define total memory[18]

// verification variables
char printline1[0xffff]={};
char *p1=printline1;
char printline2[0xffff]={};
char *p2=printline2;
char printline3[0xffff]={};
char *p3=printline3;


// determine how many characters match after a set of operations
int block(){
    block_ia=0;
    block_ib=0;
    for ( block_x=0;block_x<block_n;block_x++){
        block_o = block_op%3;
        block_op /= 3;
        if ( block_o == 0 ){ // replace
            block_ia++;
            block_ib++;
        } else if ( block_o == 1 ){ // delete
            block_ib++;
        } else { // insert
            if ( first[block_ia] ){ 
                block_ia++;
            }
        }
        while ( first[block_ia] && first[block_ia]==second[block_ib] ){ // find next mismatch
            block_ia++;
            block_ib++;
        }
        if ( first[block_ia]==0 ){
            return block_x;
        }
    }
    return block_n;
}

// find the highest-scoring set of N operations for the current string position
void bestblock(){
    best_op=0;
    best_score=0;
    la = strlen(first);
    lb = strlen(second);
    block_n = n;
    for(best_counter=0;best_counter<opmax;best_counter++){
        block_op=best_counter;
        score = n-block();
        score += block_ia-abs((la-block_ia)-(lb-block_ib));
        if ( score > best_score ){
            best_score = score;
            best_op = best_counter;
        }
    }
}

// prepare edit confirmation record
void printedit(const char * a, const char * b, int o){
    o%=3;
    if ( o == 0 ){ // replace
        *p1 = *a;
        if ( *b ){
            *p2 = 'R';
            *p3 = *b;
            b++;
        } else {
            *p2 = 'I';
            *p3 = ' ';
        }
        a++;
    } else if ( o == 1 ){ // delete
        *p1 = ' ';
        *p2 = 'D';
        *p3 = *b;
        b++;
    } else { // insert
        *p1 = *a;
        *p2 = 'I';
        *p3 = ' ';
        a++;
    }
    p1++;
    p2++;
    p3++;
    while ( *a && *a==*b ){
        *p1 = *a;
        *p2 = ' ';
        *p3 = *b;
        p1++;
        p2++;
        p3++;
        a++;
        b++;
    }
}


int main(int argc, char * argv[]){

    if ( argc < 2 ){
        printf("No file name specified\n");
        return 0;
    }

    std::ifstream file(argv[1]);
    std::string line0,line1,line2;
    std::getline(file,line0);
    std::getline(file,line1);
    std::getline(file,line2);

    // begin estimating Levenshtein distance
    best = 0;
    bestn = 0;
    for ( n=1;n<=10;n++){ // n is the number of operations that can be in a test set
        opmax = (int)pow(3.0,n);
        first = line1.c_str();
        second = line2.c_str();
        while ( *first && *first == *second ){
            first++;
            second++;
        }
        total=0;
        while ( *first && *second ){
            bestblock();
            block_n=1;
            block_op=best_op;
            block();
            total ++;
            first += block_ia;
            second += block_ib;
        }
        // when one string is exhausted, all following ops must be insert or delete
        while(*second){
            total++;
            second++;
        }
        while(*first){
            total++;
            first++;
        }
        if ( !best || total < best ){
            best = total;
            bestn = n;
        }
    }
    // done estimating Levenshtein distance

    // dump info to prove the edit distance actually comes from a valid set of edits
    if ( argc >= 3 ){
        p1 = printline1;
        p2 = printline2;
        p3 = printline3;
        n = bestn;
        opmax = (int)pow(3.0,n);
        first = line1.c_str();
        second = line2.c_str();
        while ( *first && *first == *second ){
            *p1 = *first;
            *p2 = ' ';
            *p3 = *second;
            p1++;
            p2++;
            p3++;
            first++;
            second++;
        }
        while ( *first && *second){
            bestblock();
            block_n=1;
            block_op=best_op;
            block();
            printedit(first,second,best_op);
            first += block_ia;
            second += block_ib;
        }
        while(*second){
            *p1=' ';
            *p2='D';
            *p3=*second;
            p1++;
            p2++;
            p3++;
            second++;
        }
        while(*first){
            *p1=*first;
            *p2='I';
            *p3=' ';
            p1++;
            p2++;
            p3++;
            first++;
        }

        p1 = printline1;
        p2 = printline2;
        p3 = printline3;
        int ins=0;
        int del=0;
        int rep=0;
        while ( *p1 ){
            int a;
            for ( a=0;a<79&&p1[a];a++)
                printf("%c",p1[a]);
            printf("\n");
            p1+=a;
            for ( a=0;a<79&&p2[a];a++){
                ins += ( p2[a] == 'I' );
                del += ( p2[a] == 'D' );
                rep += ( p2[a] == 'R' );
                printf("%c",p2[a]);
            }
            printf("\n");
            p2+=a;
            for ( a=0;a<79&&p3[a];a++)
                printf("%c",p3[a]);
            printf("\n\n");
            p3+=a;
        }
        printf("Best N=%d\n",bestn);
        printf("Inserted = %d, Deleted = %d, Replaced=%d, Total = %d\nLength(line1)=%d, Length(Line2)+ins-del=%d\n",ins,del,rep,ins+del+rep,line1.length(),line2.length()+ins-del);
    }

    printf("%d, Score = %0.2f\n",best,2886*100.0/best);
    system("pause");
    return 0;
}

C ++ 75.0

Program przeznaczony jest do pracy z dowolnymi ciągami tekstowymi. Mogą mieć dowolną długość, o ile żadna z nich nie przekracza 13824 znaków. Używa 1897 16-bitowych liczb całkowitych, co odpowiada 949 32-bitowych liczb całkowitych. Na początku pisałem w C, ale potem zdałem sobie sprawę, że nie ma funkcji do czytania linii.

Pierwszym argumentem wiersza polecenia powinna być nazwa pliku. Jeśli istnieje drugi argument, drukowane jest podsumowanie zmian. Pierwszy wiersz w pliku jest ignorowany, a drugi i trzeci to ciągi znaków.

Algorytm jest podwójnie zablokowaną wersją zwykłego algorytmu. Wykonuje w zasadzie tę samą liczbę operacji, ale jest oczywiście znacznie mniej dokładny, ponieważ jeśli wspólna podsekwencja zostanie podzielona na krawędź bloku, wiele potencjalnych oszczędności zostanie utraconych.

#include <cstring>
#include <inttypes.h>
#include <iostream>
#include <fstream>

#define M 24
#define MAXLEN (M*M*M)
#define SETMIN(V, X) if( (X) < (V) ) { (V) = (X); }
#define MIN(X, Y) ( (X) < (Y) ? (X) : (Y) )

char A[MAXLEN+1], B[MAXLEN+1];
uint16_t d0[M+1][M+1], d1[M+1][M+1], d2[M+1][M+1];

int main(int argc, char**argv)
{

    if(argc < 2)
        return 1;

    std::ifstream fi(argv[1]);

    std::string Astr, Bstr;
    for(int i = 3; i--;)
        getline(fi, i?Bstr:Astr);
    if(!fi.good()) {
        printf("Error reading file");
        return 5;
    }
    if(Astr.length() > MAXLEN || Bstr.length() > MAXLEN) {
        printf("String too long");
        return 7;
    }

    strcpy(A, Astr.c_str());
    strcpy(B, Bstr.c_str());

    uint16_t lA = Astr.length(), lB = Bstr.length();
    if(!lA || !lB) {
        printf("%d\n", lA|lB);
        return 0;
    }
    uint16_t nbA2, nbB2, bA2, bB2, nbA1, nbB1, bA1, bB1, nbA0, nbB0, bA0, bB0; //block, number of blocks
    uint16_t iA2, iB2, iA1, iB1, jA2, jB2, jA1, jB1; //start, end indices of block

    nbA2 = MIN(M, lA);
    nbB2 = MIN(M, lB);
    for(bA2 = 0; bA2 <= nbA2; bA2++) {
        iA2 = lA * (bA2-1)/nbA2,  jA2 = lA * bA2/nbA2;
        for(bB2 = 0; bB2 <= nbB2; bB2++) {
            if(!(bA2|bB2)) {
                d2[0][0] = 0;
                continue;
            }
            iB2 = lB * (bB2-1)/nbB2,  jB2 = lB * bB2/nbB2;
            d2[bA2][bB2] = ~0;
            if(bB2)
                SETMIN(d2[bA2][bB2], d2[bA2][bB2-1] + (jB2-iB2));
            if(bA2)
                SETMIN(d2[bA2][bB2], d2[bA2-1][bB2] + (jA2-iA2));

            if(bA2 && bB2) {
                nbA1 = MIN(M, jA2-iA2);
                nbB1 = MIN(M, jB2-iB2);
                for(bA1 = 0; bA1 <= nbA1; bA1++) {
                    iA1 = iA2 + (jA2-iA2) * (bA1-1)/nbA1, jA1 = iA2 + (jA2-iA2) * bA1/nbA1;
                    for(bB1 = 0; bB1 <= nbB1; bB1++) {
                        if(!(bA1|bB1)) {
                            d1[0][0] = 0;
                            continue;
                        }
                        iB1 = iB2 + (jB2-iB2) * (bB1-1)/nbB1, jB1 = iB2 + (jB2-iB2) * bB1/nbB1;
                        d1[bA1][bB1] = ~0;
                        if(bB1)
                            SETMIN(d1[bA1][bB1], d1[bA1][bB1-1] + (jB1-iB1));
                        if(bA1)
                            SETMIN(d1[bA1][bB1], d1[bA1-1][bB1] + (jA1-iA1));

                        if(bA1 && bB1) {
                            nbA0 = jA1-iA1;
                            nbB0 = jB1-iB1;
                            for(bA0 = 0; bA0 <= nbA0; bA0++) {
                                for(bB0 = 0; bB0 <= nbB0; bB0++) {
                                    if(!(bA0|bB0)) {
                                        d0[0][0] = 0;
                                        continue;
                                    }
                                    d0[bA0][bB0] = ~0;
                                    if(bB0)
                                        SETMIN(d0[bA0][bB0], d0[bA0][bB0-1] + 1);
                                    if(bA0)
                                        SETMIN(d0[bA0][bB0], d0[bA0-1][bB0] + 1);
                                    if(bA0 && bB0)
                                        SETMIN(d0[bA0][bB0], d0[bA0-1][bB0-1] + (A[iA1 + nbA0 - 1] != B[iB1 + nbB0 - 1]));
                                }
                            }
                            SETMIN(d1[bA1][bB1], d1[bA1-1][bB1-1] + d0[nbA0][nbB0]);
                        }
                    }
                }

                SETMIN(d2[bA2][bB2], d2[bA2-1][bB2-1] + d1[nbA1][nbB1]);
            }
        }
    }
    printf("%d\n", d2[nbA2][nbB2]);

    if(argc == 2)
        return 0;

    int changecost, total = 0;
    for(bA2 = nbA2, bB2 = nbB2; bA2||bB2; ) {
        iA2 = lA * (bA2-1)/nbA2,  jA2 = lA * bA2/nbA2;
        iB2 = lB * (bB2-1)/nbB2,  jB2 = lB * bB2/nbB2;
        if(bB2 && d2[bA2][bB2-1] + (jB2-iB2) == d2[bA2][bB2]) {
            total += changecost = (jB2-iB2);
            char tmp = B[jB2];
            B[jB2] = 0;
            printf("%d %d deleted {%s}\n", changecost, total, B + iB2);
            B[jB2] = tmp;
            --bB2;
        } else if(bA2 && d2[bA2-1][bB2] + (jA2-iA2) == d2[bA2][bB2]) {
            total += changecost = (jA2-iA2);
            char tmp = B[jA2];
            A[jA2] = 0;
            printf("%d %d inserted {%s}\n", changecost, total, A + iA2);
            A[jA2] = tmp;
            --bA2;
        } else {
            total += changecost = d2[bA2][bB2] - d2[bA2-1][bB2-1];
            char tmpa = A[jA2], tmpb = B[jB2];
            B[jB2] = A[jA2] = 0;
            printf("%d %d changed {%s} to {%s}\n", changecost, total, B + iB2, A + iA2);
            A[jA2] = tmpa, B[jB2] = tmpb;
            --bA2, --bB2;
        }
    }


    return 0;
}

Python, 100

Udało mi się idealnie wyliczyć odległość edycji w przydzielonym limicie pamięci. Niestety, ten wpis narusza dwie zasady wyzwania, w piśmie, jeśli nie w duchu.

Po pierwsze, tak naprawdę nie zapisałem moich danych w 1000 32-bitowych liczbach całkowitych. Dla ciągów o długości 10000 znaków mój program tworzy dwie tablice o długości 10000 elementów, które będą zawierały tylko +1, 0 lub -1. Przy 1,585 bitów na liczbę trójskładnikową byłoby możliwe spakowanie tych 20000 tritów w 31700 bitów, pozostawiając 300 bitów jako więcej niż wystarczającą ilość dla moich 7 pozostałych 16-bitowych liczb całkowitych.

Po drugie, nie wdrożyłem wymaganego trybu wyświetlania zmian. Alternatywnie zaimplementowałem tryb, który drukuje pełną matrycę edycji. Jest absolutnie możliwe obliczenie ścieżki edycji na podstawie tej matrycy, ale nie mam teraz czasu na jej wdrożenie.

#!/usr/bin/env python

import sys

# algorithm originally from
# https://en.wikipedia.org/wiki/Levenshtein_distance#Iterative_with_two_matrix_rows

print_rows = False
if len(sys.argv) > 2:
    print_rows = True

def LevenshteinDistance(s, t):
    # degenerate cases
    if s == t:
        return 0
    if len(s) == 0:
        return len(t)
    if len(t) == 0:
        return len(s)

    # create two work vectors of integer distance deltas

    # these lists will only ever contain +1, 0, or -1
    # so they COULD be packed into 1.585 bits each
    # 15850 bits per list, 31700 bits total, leaving 300 bits for all the other variables

    # d0 is the previous row
    # initialized to 0111111... which represents 0123456...
    d0 = [1 for i in range(len(t)+1)]
    d0[0] = 0        
    if print_rows:
        row = ""
        for i in range(len(t)+1):
            row += str(i) + ", "
        print row

    # d1 is the row being calculated
    d1 = [0 for i in range(len(t)+1)]

    for i in range(len(s)-1):
        # cummulative values of cells north, west, and northwest of the current cell
        left = i+1
        upleft = i
        up = i+d0[0]
        if print_rows:
            row = str(left) + ", "
        for j in range(len(t)):
            left += d1[j]
            up += d0[j+1]
            upleft += d0[j]
            cost = 0 if (s[i] == t[j]) else 1
            d1[j + 1] = min(left + 1, up + 1, upleft + cost) - left
            if print_rows:
                row += str(left+d1[j+1]) + ", "

        if print_rows:
            print row

        for c in range(len(d0)):
            d0[c] = d1[c]

    return left+d1[j+1]

with open(sys.argv[1]) as f:
    lines = f.readlines()

perfect = lines[0]
string1 = lines[1]
string2 = lines[2]
distance = LevenshteinDistance(string1,string2)
print "edit distance: " + str(distance)
print "score: " + str(int(perfect)*100/distance) + "%"

przykładowe dane wejściowe:

2
101100
011010

przykładowe pełne dane wyjściowe:

0, 1, 2, 3, 4, 5, 6,
1, 1, 1, 2, 3, 4, 5,
2, 1, 2, 2, 2, 3, 4,
3, 2, 1, 2, 3, 2, 3,
4, 3, 2, 1, 2, 3, 3,
5, 4, 3, 2, 1, 2, 3,
6, 5, 4, 3, 2, 2, 2,
edit distance: 2
score: 100%