Der Bearbeitungsabstand (oder Levenshtein-Abstand) zwischen zwei Zeichenfolgen ist die minimale Anzahl von Einfügungen, Löschungen und Ersetzungen einzelner Zeichen, die erforderlich sind, um eine Zeichenfolge in die andere umzuwandeln. Wenn die beiden Zeichenfolgen jeweils die Länge n haben, ist bekannt, dass dies durch dynamische Programmierung in O (n ^ 2) -Zeit erfolgen kann. Der folgende Python-Code führt diese Berechnung für zwei Zeichenfolgen s1und durch 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]

Bei dieser Aufgabe müssen Sie so nah wie möglich an der Berechnung der Bearbeitungsentfernung sein, jedoch mit einer starken Speicherbeschränkung. Ihr Code darf ein Array mit 1000 32-Bit-Ganzzahlen definieren. Dies ist der einzige temporäre Speicher, den Sie für Ihre Berechnung verwenden. Alle Variablen und Datenstrukturen sollen in diesem Array enthalten sein. Insbesondere könnten Sie den obigen Algorithmus für Zeichenfolgen mit einer Länge von 1000 nicht implementieren, da Sie mindestens 1.000.000 Zahlen speichern müssten. Wenn Ihre Sprache natürlich keine 32-Bit-Ganzzahlen enthält (z. B. Python), müssen Sie lediglich sicherstellen, dass Sie niemals eine Zahl größer als 2 ^ 32-1 im Array speichern.

Sie können die Daten mit einer beliebigen Standardbibliothek Ihrer Wahl einlesen, ohne sich über die Speicherbeschränkungen in diesem Teil Gedanken machen zu müssen. Um den Wettbewerb für den Hauptteil Ihres Codes fair zu gestalten, dürfen Sie nur Operationen verwenden, die funktional denen in der Programmiersprache C entsprechen und keine externen Bibliotheken verwenden können.

Um besonders klar zu sein, zählt der Speicher zum Speichern der Eingabedaten oder der vom Interpreter Ihrer Sprache, JVM usw. verwendete Speicher nicht zu Ihrem Limit und Sie können möglicherweise nichts auf die Festplatte schreiben. Sie müssen davon ausgehen, dass die Eingabedaten im Speicher schreibgeschützt sind, damit Sie sie nicht wiederverwenden können, um mehr Arbeitsraum zu gewinnen.

Was muss ich implementieren?

Ihr Code sollte eine Datei im folgenden Format einlesen. Es wird drei Zeilen haben. Die erste Zeile ist der wahre Bearbeitungsabstand. Die zweite ist Zeichenfolge 1 und die dritte ist Zeichenfolge 2. Ich werde sie mit den Beispieldaten unter https://bpaste.net/show/6905001d52e8 testen, wobei die Zeichenfolgen eine Länge von 10.000 haben, sie sollten jedoch nicht auf diese Daten spezialisiert sein. Es sollte den kleinsten Bearbeitungsabstand ausgeben, den es zwischen den beiden Zeichenfolgen finden kann.

Sie müssen auch nachweisen, dass Ihre Bearbeitungsentfernung tatsächlich aus einem gültigen Satz von Änderungen stammt. Ihr Code sollte einen Schalter haben, der ihn in einen Modus verwandelt, der möglicherweise mehr Speicher benötigt (so viel Sie möchten) und die Bearbeitungsvorgänge ausgibt, die Ihre Bearbeitungsentfernung angeben.

Ergebnis

Ihre Punktzahl wird die sein (optimal edit distance/divided by the edit distance you find) * 100. Beachten Sie zunächst, dass Sie eine Punktzahl erhalten können, indem Sie nur die Anzahl der Nichtübereinstimmungen zwischen den beiden Zeichenfolgen zählen.

Sie können jede Sprache verwenden, die frei verfügbar und unter Linux einfach zu installieren ist.

Krawattenbruch

Im Falle eines Unentschieden werde ich Ihren Code auf meinem Linux-Computer ausführen und der schnellste Code gewinnt.

C ++, Punktzahl 92,35

Schätzalgorithmus: Der Algorithmus findet die erste Stelle, an der sich die beiden Zeichenfolgen unterscheiden, und versucht dann alle möglichen N Operationspermutationen (Einfügen, Löschen, Ersetzen - übereinstimmende Zeichen werden übersprungen, ohne eine Operation zu verbrauchen). Jeder mögliche Satz von Operationen wird basierend darauf bewertet, wie weit dieser Satz von Operationen erfolgreich mit den beiden Zeichenfolgen übereinstimmt und wie stark die Zeichenfolgenlängen konvergieren. Nach dem Bestimmen des Satzes von N Operationen mit der höchsten Punktzahl wird die erste Operation in dem Satz angewendet, die nächste Nichtübereinstimmung wird gefunden und der Prozess wird wiederholt, bis das Ende der Zeichenfolge erreicht ist.

Das Programm versucht alle Werte von N von 1 bis 10 und wählt die Stufe aus, die die besten Ergebnisse liefert. N = 10 ist im Allgemeinen das Beste, wenn die Bewertungsmethode die Zeichenfolgenlänge berücksichtigt. Höhere Werte von N wären wahrscheinlich noch besser, würden aber exponentiell länger dauern.

Speichernutzung: Da das Programm rein iterativ ist, benötigt es sehr wenig Speicher. Nur 19 Variablen werden verwendet, um den Programmstatus zu verfolgen. Diese werden durch #defines als globale Variablen festgelegt.

Verwendung: Das Programm wird genauso verwendet wie das von feersum: Der erste Parameter wird als Datei angenommen, und alle zusätzlichen Parameter geben an, dass die Änderungen angezeigt werden sollen. Das Programm druckt immer die geschätzte Bearbeitungsentfernung und die Punktzahl.

Überprüfungsausgabe: Die Überprüfungsausgabe, die in drei Zeilen formatiert wurde:

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

Die obere Zeile ist die Zielzeichenfolge, die mittlere die Operationen und die untere die zu bearbeitende Zeichenfolge. Leerzeichen in der Operationszeile zeigen an, dass die Zeichen übereinstimmen. 'R' gibt an, dass das Zeichen der Bearbeitungszeichenfolge an dieser Position durch das Zeichen der Zielzeichenfolge ersetzt wird. 'I' gibt an, dass an der Bearbeitungszeichenfolge das Zeichen der Zielzeichenfolge an dieser Position eingefügt ist. 'D' zeigt an, dass das Zeichen an der Bearbeitungszeichenfolge an dieser Position gelöscht wurde. In die Bearbeitungs- und Zielzeichenfolgen werden Leerzeichen eingefügt, wenn in das andere Zeichen ein Zeichen eingefügt oder gelöscht wird, damit sie ausgerichtet werden.

#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

Das Programm ist für die Arbeit mit beliebigen Textzeichenfolgen ausgelegt. Sie können unterschiedlich lang sein, solange keines mehr als 13824 Zeichen enthält. Es werden 1.897 16-Bit-Ganzzahlen verwendet, was 949 32-Bit-Ganzzahlen entspricht. Zuerst schrieb ich es in C, stellte dann aber fest, dass es keine Funktion zum Lesen einer Zeile gab.

Das erste Befehlszeilenargument sollte ein Dateiname sein. Wenn ein zweites Argument vorhanden ist, wird eine Zusammenfassung der Änderungen gedruckt. Die erste Zeile in der Datei wird ignoriert, während die zweite und dritte die Zeichenfolgen sind.

Der Algorithmus ist eine doppelt blockierte Version des üblichen Algorithmus. Es führt im Grunde die gleiche Anzahl von Operationen aus, ist jedoch natürlich viel weniger genau, da ein Großteil der potenziellen Einsparungen verloren geht, wenn eine gemeinsame Teilsequenz über die Kante eines Blocks aufgeteilt wird.

#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

Ich habe es geschafft, die Bearbeitungsentfernung im zugewiesenen Speicherlimit perfekt zu berechnen. Leider verstößt dieser Eintrag gegen zwei Regeln der Herausforderung, in Buchstaben, wenn nicht im Geiste.

Erstens habe ich meine Daten nicht in 1000 32-Bit-Ints gespeichert. Für Zeichenfolgen mit 10000 Zeichen erstellt mein Programm zwei Arrays mit 10000 Zeichen, die nur +1, 0 oder -1 enthalten. Bei 1,585 Bit pro ternärer Zahl wäre es möglich, diese 20000 Tits in 31700 Bit zu packen, wobei 300 Bit mehr als genug für meine 7 verbleibenden 16-Bit-Ganzzahlen bleiben.

Zweitens habe ich den erforderlichen Modus zum Anzeigen von Änderungen nicht implementiert. Ich habe alternativ einen Modus implementiert, der die vollständige Bearbeitungsmatrix druckt. Es ist absolut möglich, den Bearbeitungspfad aus dieser Matrix zu berechnen, aber ich habe momentan keine Zeit, ihn zu implementieren.

#!/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) + "%"

Beispieleingabe:

2
101100
011010

Beispiel ausführliche Ausgabe:

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%