Tüm "karakter-eşit" dizeleri bulmak için etkili algoritma?

Question

Bir giriş dizesinin "homoglyph equivalents" çıktısını veren verimli bir işlevi nasıl yazabiliriz?

Örnek 1 (sözde kodu):

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" 
        ] 

Örnek 2:

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

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

Örnek 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" 
        ] 

Not: Çıkış dizisindeki üyelerin sıralaması önemli değildir ve verilen homofly eşlemlerin uygun olduğu varsayılabilir (girişler bize bir "sonsuz döngü" vermez).

Güncel algoritmam işe yarıyor, ancak ham bruteforcing kullanıyor ve performansı çok kötü. Örneğin. homoglyphs ["rn", "m", "nn"] ile "mmmmm" bir giriş çalıştırmak için 38 saniye sürer:

// 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); 
} 

biz verimli (hızlı) homoglyph genişletme algoritmasını uygulamak nasıl

?

Answer 1

Yinelemeli bir uygulamadan biraz performans elde etmelisiniz, ancak gerçek performansla ilgili çok düşünmedim. Bu, çıkış dizgesini birden çok kez döngüden ve her yinelemenin çıktısını saymaya devam edecektir. Ayrıca, aynı homobilgiyi iki kez hesaplamayı önlemek için küçük bir "önbellek" ekledim, basitlik için eşlemelere karşı kontrol etmiyor, ancak bunu eşlemelerin değiştiği her aramadan önce önbelleğe uygulayabilir veya önbelleği temizleyebilirsiniz (ancak çirkin ve kolayca böcekleri tanıtır).

Kod benziyor:

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 

(ben de php sözdizimi usta değilim gibi bu piton ile yazılır, ben aslında bu kadar hataları olabilir bu çalışmaz ama mantık özü