Привет, хабр!

Набирая смс или просто текст на мобильном телефоне довольно давно хотел сделать Т9 алгоритм самому.

Алгоритм понятен, но все не доходили руки.

Сегодня все же собрался и получилось сделать.

Итак первым делом нужно сформулировать то что хотелось получить.

Задача: Сделать аналог клавиатуры мобильного телефона и набирая цифры — получать список слов.
Ограничение: Особых ограничений не делалось, все таки работа для just for fun, но хочется чтобы было в районе 1 секунды парсинг.
В качестве фичи: Поддержка языков.

В качестве базы слов был взят файл с 26,000 слов.

Теперь сам алгоритм:

Мой алгоритм условно разбит на 2 части.
1 часть — выбирает все слова которые начинаются на одну из букв соответствующей цифре.
То есть для цифры 3 выбираются все слова начинающийся на d,e,f.

2 часть — последовательно проходить по всем числам и отсеивать неподходящие слова.

Поддержка языков:
Думаю всем понятно, что поддержка языков осуществляется заменой букв под цифрами.
По этому реализацию покажу ниже.

В качестве демонстрации используется jquery и эмуляция кнопок телефона.

Посмотреть можно здесь

Теперь сам класс на РНР:
class T9_Exception extends Exception {
}

abstract class T9 {
    protected $wordlist = array(); // слова которые загружаются
    protected $enum = array(); // соответсвие букв и цифр
    protected $mb_support = true; // поддержка мбстринг

    public function mb_support( $status = true ) {
        $this->mb_support = $status;
    }
    public function __construct( $filename=null ) {
        if( $filename )
            $this->load($filename); // грузим файл
    }
    public function load( $filename ) {
        if( file_exists($filename) && is_readable($filename)) {
            $this->wordlist = file($filename);
            //array_walk( $this->wordlist, create_function('&$w', '$w=trim($w);')); // замедляет работу пришлось отключить
            return ;
        }
        throw new T9_Exception("Can not read $filename", 100);

    }
    /**
     * Fetch data from wordlist
     * @param string $input
     * @return array
     */
    public function fetch($input) {
        $compare = array();
        $total = count($this->wordlist);
        for($i=0;$i<$total;$i++) {
            $len = strlen($this->enum[$input[0]]);
            for($j=0;$j<$len;$j++) {
                if( $this->mb_support == true ) {
                    if( mb_strpos($this->wordlist[$i], $this->enum[$input[0]][$j]) === 0)
                        $compare[]=$this->wordlist[$i];
                }
                else {
                    if( strpos($this->wordlist[$i], $this->enum[$input[0]][$j]) === 0)
                        $compare[]=$this->wordlist[$i];
                }

            }
        }
        for($i=1;$i<strlen($input);$i++) {
            $found = false;
            $newcompare = array();
            for($k=0;$k<count($compare);$k++) {
                for($j=0;$j<strlen($this->enum[$input[$i]]);$j++) {
                    $letter = $this->enum[ $input[$i] ][$j];
                    if( $this->mb_support == true) {
                        if( mb_strtolower($compare[$k][$i]) == $letter)
                            $newcompare[] = $compare[$k];
                    }
                    else {
                        if( $compare[$k][$i] == $letter)
                            $newcompare[] = $compare[$k];
                    }



                }
            }
            $compare = $newcompare;
        }
        return $compare;
    }
}


class T9_English extends T9 {

    protected $enum = array(
            0 => '',
            1 => '',
            2 => 'abc',
            3 => 'def',
            4 => 'ghi',
            5 => 'jkl',
            6 => 'mno',
            7 => 'pqrs',
            8 => 'tuv',
            9 => 'wxyz',
    );
}

class T9_Russian extends T9 {
    protected $enum = array(
            0 => '',
            1 => '',
            2 => 'абвг',
            3 => 'деёжз',
            4 => 'ийкл',
            5 => 'мноп',
            6 => 'рсту',
            7 => 'фхцч',
            8 => 'шщъы',
            9 => 'ьэюя',

    );
}

UPD: некоторые байты пропали при выводе, по этому выложил исходник так же по этой ссылке:
http://anton.in.ua/demo/t9/t9.txt

Русский словарь проверять не стал, но судя по алгоритму должно работать так же.

Вот такая небольшая разминка для ума.

Всем спасибо за внимание.