Hashberechnung der Topologie eines Wortes - wie?

[helgew]

so, ich habe mich nun dazu entschlossen, maximal 15 sich wiederholende Zeichentypen zuzulassen, bevor Informationsverlust auftritt, dafür kann ich die Aussage in einen uint64 stopfen. Jedes sich wiederholende Zeichen wird mit 4 bit codiert, für en Fall, dass es mehr als 16 Wiederholungen gibt, gehe ich davon aus, dass es wenige Worte mit mehr als 16 verschiedenen Zeichen gibt. Kollisionen sind also sehr unwahrscheinlich und der Kostenfaktor für die Berechnung des Kontrollwertes ist nicht allzuhoch.

Delphi-Quellcode:

  type TMetaListEntry = packed record
    len : integer;    // trivial length
    rephash: uint64; // assign ascending prime numbers to character places, form product
    fourcc: cardinal; // first four characters as bytes
    seq: uint64;
    case fastaccess:boolean of
      true :(repchars         : dword); // count reoccuring characters as unique and in total
      false:(repunique,repcnt :  word);
  end;

const primetable : array [1..58] of integer = (
  2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,
 61,67,71,73,79,83,89,97,101,103,107,109,113,127,
 131,137,139,149,151,157,163,167,173,179,181,191,
 193,197,199,211,223,227,229,233,239,241,251,257,
 263,269,271);
var 
  charhistogram: array[0..255] of byte;
  charID       : array[0..255] of byte;

function WordProfile(w: string): TMetaListEntry;
var
  i: integer;
  pa: PByteArray;
  pc: ^Cardinal absolute pa;
  o: integer;
  cid: integer; // repeated character ID (4-bit value), assume <=15 repeating chars
  seqshift: uint64;
begin
  result.len := length(w);
  ZeroMemory(@charhistogram[0],256);
  result.repchars := 0;
  result.rephash  := 1;
  result.seq      := 0;

  cid := 1;
  for i := 1 to result.len do
  begin
    o := ord(w[i]);
    inc(charhistogram[o]);
    if charhistogram[o] > 1 then
    begin
      inc(result.repcnt);
      if charhistogram[o] = 2 then
      begin
        inc(result.repunique);
        charID[o] := cid and $0F;
        inc(cid);
      end;
    end;
  end;

  seqshift := 1;
  for i := 1 to result.len do
  begin
    o := ord(w[i]);
    if charhistogram[o] > 1 then
    begin
       result.rephash :=  result.rephash * primetable[i];
       result.seq := result.seq or (charID[o] * seqshift);
       seqshift := seqshift shl 4;
    end;
  end;

  pa := @w[1];
  case result.len of
    1: result.fourcc := pa[0];
    2: result.fourcc := pa[0] + pa[1]*$100;
    3: result.fourcc := pa[0] + pa[1]*$100 + pa[2]*$10000;
    else result.fourcc := pc^;
  end;
end;

als nächstes bräuchte ich einen Wortgenerator, der aus einer Art regulärer Ausdrücke Zeichenfolgen generiert und dann das processing für ganze Sätze. Es wird...

Anwendungsbeispiel: Suchwort "1234567268767", pro Zahl ein unbekannter Buchstabe

Code:

length: 13
repetitions: 5 (3)
rep hash: 740277849
sequ64: 0x0000000032321321

matching words: 1
_____________________
klavierlehrer

--------- Problem gelöst! ----------