Привет, хабр!
Набирая смс или просто текст на мобильном телефоне довольно давно хотел сделать Т9 алгоритм самому.
Алгоритм понятен, но все не доходили руки.
Сегодня все же собрался и получилось сделать.
Итак первым делом нужно сформулировать то что хотелось получить.
Задача: Сделать аналог клавиатуры мобильного телефона и набирая цифры — получать список слов.
Ограничение: Особых ограничений не делалось, все таки работа для just for fun, но хочется чтобы было в районе 1 секунды парсинг.
В качестве фичи: Поддержка языков.
В качестве базы слов был взят файл с 26,000 слов.
Теперь сам алгоритм:
Мой алгоритм условно разбит на 2 части.
1 часть — выбирает все слова которые начинаются на одну из букв соответствующей цифре.
То есть для цифры 3 выбираются все слова начинающийся на d,e,f.
2 часть — последовательно проходить по всем числам и отсеивать неподходящие слова.
Поддержка языков:
Думаю всем понятно, что поддержка языков осуществляется заменой букв под цифрами.
По этому реализацию покажу ниже.
В качестве демонстрации используется jquery и эмуляция кнопок телефона.
Посмотреть можно здесь
Теперь сам класс на РНР:
UPD: некоторые байты пропали при выводе, по этому выложил исходник так же по этой ссылке:
http://anton.in.ua/demo/t9/t9.txt
Русский словарь проверять не стал, но судя по алгоритму должно работать так же.
Вот такая небольшая разминка для ума.
Всем спасибо за внимание.
Набирая смс или просто текст на мобильном телефоне довольно давно хотел сделать Т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
Русский словарь проверять не стал, но судя по алгоритму должно работать так же.
Вот такая небольшая разминка для ума.
Всем спасибо за внимание.
