Dubletten-Funktion: Dubletten in einem Array

[wolfram]

Hallo,
Ich moechte eine Dublettensuchfunktion für einen string-Array programmieren.
Die dublettenfunktion soll eine Art "matching factor" (t) zurueckgeben, so dass
die Übereinstimmung gemessen werden kann. ist t = 0 stimmen die strings 100% ueberein,
bei t=1 unterscheiden sie sich an einer stelle...

Haette jemand einen anderen Vorschlag nach dubletten in einem String zu suchen?
Oder eine function in Assembler, die das ganze beschleunigen wuerde?

Danke!

----------------

Bis jetzt habe ich mir folgenden Ablauf überlegt:

for x := 1 to "Groesse des Array" do

...
for y := 1 to "Groesse des Array" do
...
if (x<>y) then
t := doublette(array[x],array[y]);
if (t=Festgelegtes t, welches nicht ueberschritten werden darf) then
dublette := true //oder aehnlich
end;
end;

end;

//uses math;

function dublette(a,z):integer;
var x,t,Zmin:integer;
begin
Zmin := Min(length(a), length(z));

for x := 1 to zMin do
begin
if (a[x]=z[x]) then inc(t);
...

result := zMin-t;
end

[Ultimator]

1.) Das müsste eigentlich so in Ordnung sein, denke ich.
2.) Nimm doch bitte die [ delphi ]-Tags ;-)

[rantanplan99]

Naja, nen richtigen Vorschlag hab ich nicht, aber optimier mal deine for Schleifen

Delphi-Quellcode:

for x := 1 to "Groesse des Array" do
  ...
  for y := i+1 to "Groesse des Array" do
    ...
    t := doublette(array[x],array[y]);
    if (t=Festgelegtes t, welches nicht ueberschritten werden darf) then dublette := true //oder aehnlich
  end;
end;

end;

verkürzt die 2te for-Schleife, weil wenn array[1] und array[2] verglichen hast, musst du ja nicht später nochmal array[2] mit array[1] vergleichen.

wenn die 2te for-Schleife mit i+1 anfängt sparst du dir das if x<>y

NACHTRAG:
Achja, die erste for-Schleife dann natürlich nur bis "Groesse des Array -1"

[Robert Marquardt]

Der zugehoerige Algorithmus nennt sich Levensthein-Distanz.

[wolfram]

danke für die schnellen antworten!

aber die funktion in assembler zu programmieren wuerde keinen geschwindigkeitszuwachs bringen? ich muss immerhin 100 000 datensaetze in den array einlesen und dann vergleichen!

[Robert Marquardt]

Die for-Schleifen sind jetzt ja optimiert. Assembler bringt bei denen garnichts.
Die Levenshtein-Distanz sollte erst mal funktionieren, dann kann man ueber Assembler vielleicht nachdenken.
Ich bezweifle aber das Assembler hilft. Levenshtein ist einfache lineare Optimierung.