Решал я такую задачку: есть строка набранная в манере T9 - типа "233 364", которое расшифровывается как "bad dog" (2 = abc, 3 = def ... как клавиши на телефоне). Есть словарь, в котором даны слова и частоты их встречаемости. Частоты нужны на случай, если подойдет несколько слов (223 может быть dog или add) - тогда выбирается наиболее часто встречающееся. Я делал прогу, которая читает строку T9 и превращает ее в нормальный текст. Алгоритм выбрал простой: разбиваем строку на слова, читаем слово - его отыскиваем в словаре. Чтобы поиск по словарю был быстрым я сделал из него дерево. Например слово add в нем будет размещено так: root -> 2 -> 3 -> 3 , цифры - это номера клавиш для букв: первая буква (Add) - 2, вторая (aDd) - 3, третья (adD) снова 3. В том же узле 2->3->3 где висит слово add, висит и слово bad и другие слова, которые подходят под описание 233. Имея такое дерево, можно очень быстро найти список вариантов для любой комбинации (тем более, что в слове не больше 20 букв). Надо сказать, что до этого я пробовал брутфорс для поиска в словаре подходящих комбинаций: время на обработку словаря нулевое, но поиск был слишком долгим на больших строках - программа конкурсная, строка могла содержать до 100000 символов, а уложиться надо было в лимит 1.5 секунд. Построение дерева закономерно дало огромный выигрыш во времени поиска, но возникла другая проблема - теперь программа выходила за лимит при больших объемах словаря: я так понял, дерево потому что долго строилось. Дерево я строил рекурсивно, в виде связанных списков, код рекурсивной функции внизу. И как ускорить алгоритм его построения я не знаю. Может кто знает способы?
| Код |
/*************************************************************************
* class Node
* узел дерева
*/
class Node{
int buttonN; /* номер клавиши */
Node son; /* потомок */
Node brother; /* соседний узел на том же уровне */
boolean youngest; /* true если это последний узел на этом уровне (тогда brother будет ссылаться на предка - для удобства) */
WordLink chainHead; /* односвязный список, каждый WordLink содержит собственно слово и ссылку next - не следующее слово спска*/
public Node(int buttonN, Node son, Node brother, boolean youngest){
this.buttonN = buttonN;
this.son = son;
this.brother = brother;
this.youngest = youngest;
}
}
/*************************************************************************
* addWord
* добавляет новое слово в дерево
*
* @param tree
* @param linkToAdd
* @param position
*/
public void addWord(Node tree, WordLink linkToAdd, int position){
int currentButton = 0;
try {
currentButton = getButton(linkToAdd.word.charAt(position - 1)); // getButton возвращает номер клавиши, которой соответствует символ
} catch (Exception e) {e.printStackTrace(); return;}
/* Если буква совпала то ветка подходит */
if (tree.buttonN == currentButton){
/* Если это последняя буква слова, то мы на месте */
if (position == linkToAdd.word.length()){
linkToAdd.next = tree.chainHead; /* добавляем слово в голову списка */
tree.chainHead = linkToAdd;
/* Если не последняя - передаем сыну */
} else {
/* Если сына нет еще, то создаем сына под следующую букву */
if (tree.son == null){
int nextButton = 0;
try {
nextButton = getButton(linkToAdd.word.charAt(position));
} catch (Exception e) {e.printStackTrace(); return; }
Node newSon = new Node(nextButton, null, tree, true);
tree.son = newSon;
}
/* собственно, передаем*/
addWord(tree.son, linkToAdd, position + 1);
}
/* Если буква не совпала - надо передать брату, пока не совпадет */
} else {
/* Если дальше брата нет, то создадим нужного,
* братьев будет не больше 9 (на 9 кнопок)
* */
if (tree.youngest){
Node newBrother =
new Node(currentButton, null, tree.brother, true);
tree.brother = newBrother;
tree.youngest = false;
}
/* собственно, передаем */
addWord(tree.brother, linkToAdd, position);
}
}
|
|