Effizienter Algorithmus zum Auffinden aller "character-equal" -Strings?

Question

Wie können wir eine effiziente Funktion schreiben, die „homoglyph equivalents“ von einer Eingabezeichenfolge ausgibt?

Beispiel 1 (Pseudocode):

homoglyphs_list = [ 
        ["o", "0"], // "o" and "0" are homoglyphs 
        ["i", "l", "1"] // "i" and "l" and "1" are homoglyphs 
        ] 

input_string = "someinput" 
output   = [ 
        "someinput", "s0meinput", "somelnput", 
        "s0melnput", "some1nput", "s0me1nput" 
        ] 

Beispiel 2:

homoglyphs_list = [ 
        ["rn", "m", "nn"], 
        ] 

input_string = "rnn" 
output   = ["rnn", "rm", "mn", "rrn", "nnn", "nm", "nrn"] 

Beispiel 3:

homoglyphs_list = [ 
        ["d", "ci", "a"], // "o" and "0" are homoglyphs 
        ["i", "l", "1"] // "i" and "l" and "1" are homoglyphs 
        ] 
        /* 
        notice that with the two rules above, 
        we can infer "d" = "ci" = "a" = "cl" = "c1" 
        */ 

input_string = "pacerier" 
output   = [ 
        "pacerier", "pacerler", "pacer1er", "pcicerier", 
        "pcicerler", "pcicer1er", "pclcerier", "pc1cerier", 
        "pclcerler", "pc1cerler", "pclcer1er", "pc1cer1er", 
        "pdcerier", "pdcerler", "pdcer1er" 
        ] 

Hinweis: Die Reihenfolge der Elemente in der Ausgangsanordnung nicht wichtig ist, und wir können davon ausgehen, dass die angegebenen Homoglyph Zuordnungen angenommen werden richtige (Eingänge würden uns nicht gibt eine „Endlosschleife“) sein.

Mein aktueller Algorithmus funktioniert, aber es ist mit rohem bruteforcing und Leistung ist schrecklich. Z.B. eine Eingabe von "mmmmm" mit Homoglyphen ["rn", "m", "nn"] dauert 38 Sekunden laufen:

// This is php code (non-pseudo just so we could test the running time), 
// but the question remains language-agnostic 

public function Func($in, Array $mappings){ 
    $out_table = array(); 
    $out_table[$in] = null; 
    while(true){ 
     $number_of_entries_so_far = count($out_table); 
     foreach(array_keys($out_table) as $key){ 
      foreach($mappings as $mapping){ 
       foreach($mapping as $value){ 
        for($a=0, $aa=strlen($key); $a<$aa; ++$a){ 
         $pos = strpos($key, $value, $a); 
         if($pos === false){ 
          continue; 
         } 
         foreach($mapping as $equal_value){ 
          if($value === $equal_value){ 
           continue; 
          } 
          $out_table[substr($key, 0, $pos) . $equal_value . substr($key, $pos + strlen($value))] = null; 
         } 
        } 

       } 
      } 
     } 
     if($number_of_entries_so_far === count($out_table)){ 
      // it means we have tried bruteforcing but added no additional entries, 
      // so we can quit now 
      break; 
     } 
    } 
    return array_keys($out_table); 
} 

Wie können wir einen effizienten (schnellen) Homoglyph Expansionsalgorithmus implementieren? obwohl

Answer 1

Sie sollten einige Leistung aus einer rekursiven Implementierung gewinnen, habe ich nicht viel in die tatsächliche Leistung Gedanken gemacht. Dies würde dazu führen, dass die Ausgabezeichenfolge mehrmals durchlaufen und die Ausgabe bei jeder Iteration gezählt wird. Außerdem habe ich einen kleinen "Cache" hinzugefügt, um zu verhindern, dass die gleiche Homoglyphe zweimal berechnet wird. Der Einfachheit halber prüft sie nicht die Zuordnungen, aber Sie können sie implementieren oder den Cache vor jedem Aufruf löschen, bei dem sich Zuordnungen ändern (aber das ist hässlich und bringt leicht Bugs).

-Code wie folgt aussieht:

cache = {} 
def homoglyph(input_string, mappings): 
    output = [] 
    character = input_string[0] 
    if input_string in cache: 
     return cache[input_string] 
    elif not input_string: 
     return [] 
    for charset in mappings: 
     if character in charset: 
      temp = input_string 
      sub_homoglyphs = homoglyph(input_string[1:], mappings) 
      for char in charset: 
       temp[0] = char 
       output.append(temp) 
       #adding the homoglyph character to the rest of the string 
       for subhomoglyph in sub_homoglyphs: 
        output.append(char+subhomoglyph) 
    cache[input_string] = output 
    return output 

(Das mit Python geschrieben ist, wie ich in PHP-Syntax versiert nicht gut bin, habe ich nicht wirklich diese laufen, so kann es Fehler, aber der Kern der Logik da ist)