Ein Exkurs zu Algorithmenproblemen
Das Problem
Erster Schritt zur Problemlösung ist natürlich die Erkenntnis des eigentlichen Problems. Für viele Probleme, denen man in einschlägigen Foren im Web begegnet, ist dieser Schritt der wichtigste bzw. derjenige, an dem viele scheitern, weil sie ihn nicht sehen.
Was will ich? Wie exakt ist das zu definieren, was ich als Eingabe erwarte, was will ich exakt herausbekommen? Auch in diesem Fall war das von Anfang an nicht hundertprozentig klar angegeben. Der Versuch, ein Problem mit Programmquelltexten zu erklären, ist in der Regel nicht die beste Idee, besonders dann nicht, wenn die Umsetzung fehlgeschlagen oder nicht zufriedenstellend ist.
Die hinreichende Definition dieses speziellen Problems lässt sich wie folgt ausdrücken: Gegeben sind 2 Dateien A und B, die Zeichenketten in fixierter Länge beinhalten, getrennt durch Newlines. Eigentlich ist die Qulle dieser unsortierten Listen aber irrelevant, wichtig ist, dass wenn in Datei A die Zeichenketten 5 Zeichen lang sind, sind die in Datei B auch so lang. Gesucht wird nun nach dem Zeilenpaar (bzw. Paar von Strings), das die meisten Übereinstimmungen hat, wobei Übereinstimmungen bedeuten, dass an gleicher Position im String das gleiche Zeichen steht.
Bezeichnen wir die Anzahl der Zeichen als l, die Anzahl der Strings in Datei A als n, die in B als m.
A = { 'abc' , 'def' , 'acf' }
B = { 'Xbc' , 'def' }
Gesucht = { 'def' , 'def' } #3 Übereinstimmungen
Vorbetrachtungen / bereits gemachte Fehler
In den Ansätzen und Vorschlägen, die dazu zunächst gemacht wurden, fanden sich wiederholt Fehler. Fehler in der Hinsicht, dass es hier um eine effiziente Lösung ging, also war es nicht möglich, alle Daten wiederholt in Arrays zu lesen oder Dateien wiederholt zu öffnen. Im Weiteren wird noch entschieden werden müssen, ob es vetretbar ist, alle Informationen in den Speicher zu lesen (z.B. falls sortiert oder nur "geordnet" werden muss). Da die Strings fixierte Länge haben, lassen sich aber via seek() und tell() u.U. günstige Operationen direkt in der Datei durchführen, ohne den Speicher zu belasten.
Auch ist bekannt, dass in A und B zwar viele tausende Strings stehen, aber ihr Alphabet kaum so umfangreich ist, dass nicht auch Strings innerhalb einer Liste sehr ähnlich sind. Ein bis dato nicht Bedachter Effizenzgewinn kann es sein, ähnliche Strings zu gruppieren, um für den nächsten String jedes Zeichen neu zu vergleichen. O(n*m*l) worst case lässt sich vielleicht (wird sich zeigen) nicht vermeiden, aber der schlimmste Fall tritt womöglich niemals ein. Auch kann man u.U. duch Ordnung Stringpaare ausschliessen, die das bisherige Maximum an Übereinstimmungen nicht mehr übersteigen können.
Die spezielle Schwierigkeit
Die Herausforderung ist, dass zwei Strings stest auf alle zeichen überprüft werden. Ein Prefix-Baum ist also nicht die richtige Lösung, da eben nicht abgebrochen wird, wenn ein Zeichen nicht stimmt. Der Vergleich jedes Strings mit jedem für jedes Zeichen ist aber nicht zufriedenstellend, da doch so viele Ähnlichkeiten zwischen den Zeichenketten bestehen, die man nutzen sollte, um eine average-case Komplexität von weniger als O(n*m*l) zu erhalten.
Eine andere Art von Datenstruktur bietet sich aber an. Hierbei wird eine der Listen komplett gelesen (A). Es wird ein Array von l Elementen angelegt. Der Wert ist dabei selbst ein Array bzw. Hash, das jedem Zeichen eine Liste von korrespondierenden Stringpositionen in A. So kann jeder String in B Zeichen für Zeichen gezielt die Positionen der passenden Strings in A finden, ohne linear suchen zu müssen, sondern über direkten Zugriff. Es ergibt sich die Komplexität n*l + m*l = O(m*l) ( m und n sind im i.d.R. gleich, anonsten sei n stets kleiner ) , was schon bedeutend schneller ist als die ersten Annahmen andeuteten.
Datenstruktur P nach Verarbeitung von Liste A: P[ 0 ][ a ] = [0,2] P[ 0 ][ d ] = [1] P[ 1 ][ b ] = [0,2] P[ 1 ][ e ] = [1] P[ 2 ][ c ] = [0] P[ 2 ][ f ] = [1,2]
Mit Hilfe von Perls Hashes lässt sich der Zugriff auf diese Struktur in O(1) realisieren. Aber auch ohne können logarithmische Komplexitäten (Zuordnungsarrays sortiert) erreicht werden.
Umsetzung
Die Umsetzung ist nun nur noch Formsache.
my ($fileA,$fileB) = qw/dummy1 dummy2/;
open my $fa, '<' , $fileA or die $!;
open my $fb, '<' , $fileB or die $!;
my $len = do {
local $_ = <$fa>;
length($_) - 1
};
seek $fa,0,0;
sub getrecord {
my ($fh,$pos) = @_;
seek $fh,$pos*$len,0;
local $_ = <$fh>;
chomp;
$_
}
#
# P aus A initialisieren
#
my @p = ();
$p[$_] = {} for 0 .. $len-1;
{
my $rec_num = 0;
while(defined( local $_ = <$fa> )){
chomp;
my @ch = split//;
for my $i ( 0 .. $len-1 ){
push @{ $p[$i]{ $ch[$i] } } => $rec_num;
}
++ $rec_num
}}
#
# durch B arbeiten
#
my $max = 0;
my ($max_a,$max_b); #indices
{
my $rec_num = 0;
while(defined( local $_ = <$fb> )){
chomp;
my @ch = split//;
my %save = ();
my $corr = 0;
for my $i ( 0 .. $len-1 ){
last if $len-$i-1 < $max-$corr;
if( exists $p[$i]{ $ch[$i] } ){
$corr++;
$save{$_}++ for @{ $p[$i]{ $ch[$i] } };
}
}
if($corr){
for(keys %save){
if($save{$_} == $corr){
($max,$max_a,$max_b) = ($corr,$_,$rec_num)
}
}
}
++ $rec_num;
}}
#
# Ergebnis
#
printf "A-%d %s - B-%d %s : %d\n",
$max_a , getrecord($fa,$max_a),
$max_b , getrecord($fb,$max_b),
$max
;
close $fa;
close $fb;