Given an ASCII string, replace all ASCII chars with their Cyrillic equivalents

Question

The objective of the following PHP function is simple: given an ASCII string, replace all ASCII chars with their Cyrillic equivalents.

As can be seen, certain ASCII chars have two possible equivalents.

For example: if the function is fed the string "dvigatel" it should get you "двигател".

The problem: if I pass "dvigat", the function will finish its execution in a fairly reasonable amount of time.

But, if I pass "dvigatel", which is only a couple letters longer, the execution time exceeds my 30 second PHP execution time limit.

Could anybody give me a few pointers here, what's wrong with this function, why does it run so slow with an 8-char string?

function transliterate($query) {
 $map=array(
 "a" => array("а", "ъ"),
 "b" => "б",
 "c" => array("с", "ц"),
 "d" => "д",
 "e" => "е",
 "f" => "ф",
 "g" => array("г", "ж"),
 "h" => "х",
 "i" => array("и", "й"),
 "j" => array("дж", "й"),
 "k" => "к",
 "l" => "л",
 "m" => "м",
 "n" => "н",
 "o" => "о",
 "p" => "п",
 "q" => "я",
 "r" => "р",
 "s" => "с",
 "t" => "т",
 "u" => array("ъ", "ю", "у"),
 "v" => array("в", "ж"),
 "w" => "в",
 "x" => array("кс", "х"),
 "y" => array("ъ", "у"),
 "z" => "з"
 );
 $query_array = preg_split('/(?<!^)(?!$)/u', $query );
 $en_letters=array_keys($map);
 $this->processed[]=$query;
 foreach ($query_array as $letter) {
 if (in_array($letter, $en_letters)) {
 if (!is_array($map[$letter])) {
 $query_translit=str_replace($letter, $map[$letter], $query);
 } else {
 foreach ($map[$letter] as $bg_letter) {
 $query_translit=str_replace($letter, $bg_letter, $query);
 if (!in_array($query_translit, $this->transliterations)) $this->transliterations[]=$query_translit;
 }
 }
 } else {
 $query_translit=$query;
 }
 if (!in_array($query_translit, $this->transliterations)) $this->transliterations[]=$query_translit;
 }
 foreach ($this->transliterations as $transliteration) {
 if (!in_array($transliteration, $this->processed)) {
 if (!preg_match("/[a-zA-Z]/", $transliteration)) {
 return;
 } else {
 $this->transliterate($transliteration);
 }
 }
 }
 }

• Baba: 1. If there are 2 options .. how do you resolve witch one to select ... 2. Why not do a simple replace instead of a recursive function ???
• Boyan Georgiev: @Baba, it shouldn't resolve to select one. Rather, it should push both possible combinations into the resulting array. To your second, question - I was just considering it.

Answer 1

Why a recursive function for such a simple task?

$in = 'This is your input';
$map = 'your char translation array here';
$out = '';
for($i = 0; $i < strlen($in); $i++) {
 $char = $in[$i];
 if (isset($map[$char])) {
 if (is_array($map[$char])) {
 $newchar = $map[$char][0]; // whatever your multi-char selection logic is...
 } else
 $newchar = $map[$char];
 }
 $out .= $newchar;
 }
}

• Boyan Georgiev: your code is much better than what I had. Thank you.