Доброго времени суток! Идея разбора данной задачи возникла на фоне обращения ко мне ученика на одном из ресурсов, где я выступаю в качестве frontend-ментора, с просьбой разобрать одну задачу. Суть задачи состояла в следующем:
Найти все доступные комбинаций предложений, полученных методом T9 (predictive text)
Вводные данные:
Файл combinations.txt, в котором описаны последовательности цифр, имитирующие пользовательский ввод:
Файл dictionary.txt, в котором представлен список английских слов, который используется для предсказания заданного слова из последовательности выше.
Выходные данные:
Файл output.txt, в котором собраны все возможные варианты предложений.
Разбор задачи
Первое, что приходит на ум, так это использовать префиксные деревья. А перед этим стоит пояснить что же это такое.
Префиксное дерево — структура данных для хранения строк, построенная в виде дерева, где на ребрах записаны символы, а некоторые вершины помечены как конечные. Классически данная структура может быть представлена изображением ниже:
Префиксное дерево проще всего хранить в виде ссылок на вершины. Каждая вершина обычно содержит информацию о том, является ли она конечной, ссылки на связаные вершины, а также любая дополнительная информация, зависящая от задачи.
Для латинского алфавита префиксное дерево может быть реализовано по приниципу ниже.
Перед тем как реализововывать дерево, в начале нам понадобится определить карту соответствия букв цифрам в раскладке клавиатуры кнопочного телефона:
Далее приступим к реализации непосредственно префиксного дерева. Для этих целей заведем класс Trie, который реализует два основных метода insert и getPredictions. Здесь вставка работает путем обхода дерева в соответствии со строкой, которая должна быть вставлена, а затем в суффикс строки добавляются новые узлы, не содержащиеся в дереве. Метод getPredictions работает путем прохода от корня по символам слова. Если в конце оказывается, что вершина конечна — то слово найдено, в противном случае нет.
import { keyMap, rootGenerator } from "./helpers";
import { Root, Prediction } from './interfaces';
class Trie {
root: Root;
constructor() {
this.root = rootGenerator();
}
insert(word: string): void {
if (word.length === 0) throw new Error("A word has to be specified");
let currentNode = this.root;
Array.from(word).forEach((letter, index) => {
const digit = keyMap[letter];
let isLastNode = false;
if (word.length === index + 1) isLastNode = true;
if (!digit) throw new Error("Not a valid digit");
if (!currentNode.children) currentNode.children = {};
if (!currentNode.children[digit]) currentNode.children[digit] = rootGenerator();
currentNode = currentNode.children[digit] as Root;
if (!isLastNode) currentNode.predictions.deep.push(word);
});
currentNode.predictions.current.push(word);
}
getPredictions(keyString: string): Prediction | undefined {
const state = rootGenerator().predictions;
let currentNode = this.root;
let predictions;
Array.from(keyString).forEach((nodeKey) => {
if (!currentNode.children || !currentNode.children[nodeKey]) {
predictions = state;
return;
}
currentNode = currentNode.children[nodeKey] as Root;
predictions = currentNode.predictions;
});
return predictions;
}
}
export default Trie;
Теперь реализуем класс для заполнения дерева и разбора словаря. Тут нет каких-то уникальных моментов, поэтому без комментариев.
import { readFileSync } from "fs";
import Trie from "./trie";
import { rootGenerator } from "./helpers";
import { Prediction } from "./interfaces";
class TrieParser {
trie: Trie;
filePath: string;
constructor(filePath: string) {
this.trie = new Trie();
this.filePath = filePath;
}
createTrie(words?: string[]): void {
const wordArray = words || this.parseDictionary();
// Creating trie from words array
wordArray.forEach((word) => {
this.trie.insert(word);
});
}
parseDictionary(): string[] {
const filePath = this.filePath;
const data = readFileSync(filePath, {
encoding: "utf8",
});
const regex = /\r?\n/;
const array = data.toString().split(regex);
return array;
}
getPredictions(keyString: string): Prediction | undefined {
if (!keyString) return rootGenerator().predictions;
return this.trie.getPredictions(keyString);
}
}
export default TrieParser;
Дело за малым — определиться, каким образом можно получить списки всех доступных комбинаций. Классический подход к генерации таких списков — алгоритм кучи, однако в нашем случае он не подходит, потому что мы хотим получить только уникальные варианты, а поэтому наиболее подходящий вариант — декартово произведение, реализация которого будет выглядеть следующим образом:
export function cartesian<T>(...words: T[][]): T[][] {
// iteratively get the cartesian product
return words.reduce<T[][]>(
// part - cartesian product of the first few arrays from words
(part, array) =>
part.flatMap((cartesianPart) =>
//cartesianPart is an array-prefix of one of the elements of the cartesian product
array.map((element) => [...cartesianPart, element])
),
[[]]
);
}
На этом самая сложная часть заканчивается, и осталось только вызвать реализованные методы. Код с комментариями находится ниже:
import { readFileSync, createWriteStream, unlinkSync, existsSync } from "fs";
import { cartesian } from "./utils/cartesian";
import TrieParser from "./trie/trie-parser.js";
const dictionaryFilePath = "src/data/dictionary.txt";
const combinationsFilePath = "src/data/combinations.txt";
const outputFilePath = "src/data/output.txt";
const trieDictionaryInstance = new TrieParser(dictionaryFilePath);
trieDictionaryInstance.createTrie();
export function main() {
try {
if (existsSync(outputFilePath)) unlinkSync(outputFilePath);
// create file stream
const output = createWriteStream(outputFilePath, {
flags: "a",
});
const rawData = readFileSync(combinationsFilePath, { encoding: "utf-8" })
.toString()
.split(/\r?\n/);
for (const rawCombination of rawData) {
const combinations = rawCombination.split(" ");
const predictionArray: string[][] = combinations.map((combination) => {
// Get predictions for each combination in the string
const result = trieDictionaryInstance.getPredictions(combination);
const targetArray = result?.current.flatMap((item) =>
Array.isArray(item) ? item : [item]
);
return targetArray;
}) as string[][];
// Get cartesian products
const possibleProducts = (
[...cartesian(...(predictionArray as [string[]]))] as string[][]
).map((permutation) => permutation.join(" "));
for (const permutation of possibleProducts) {
output.write(permutation + "\r");
}
}
output.end();
} catch (e) {
console.error(e);
}
}
main();
Код задачи доступен на моем гитхаб. Спасибо за внимание!
Сохраню статью и буду показывать её всем знакомым, которые будут говорить, что хотят "войти в айти". Это показательный пример склада ума, если можно так сказать, который должен быть, чтоб тебе было интересно в этой профессии.
Сохраню статью и буду показывать её всем знакомым, которые будут говорить, что хотят "войти в айти". Это показательный пример склада ума, если можно так сказать, который должен быть, чтоб тебе было интересно в этой профессии.