Effizienter Algorithmus zum Auffinden aller "zeichengleichen" Zeichenfolgen?
Wie können wir eine effiziente Funktion schreiben, die ausgibt "Homoglyphenäquivalente"einer Eingabezeichenfolge?
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 im Ausgabearray ist nicht wichtig, und wir können davon ausgehen, dass die angegebenen Homoglyphen-Zuordnungen wie folgt aussehenrichtig (Eingaben würden uns keine "Endlosschleife" geben).
Mein aktueller Algorithmus funktioniert, aber er verwendet rohe Bruteforcing und die Leistung ist schrecklich. Z.B. eine Eingabe von"mmmmm"
mit Homoglyphen["rn", "m", "nn"]
dauert 38 Sekunden zu 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) Homoglyphenexpansionsalgorithmus implementieren?