Привет, Хабр! На днях ко мне обратился ученик на одном из ресурсов, где я выступаю в качестве frontend-ментора, с просьбой разобрать одну задачу. Суть задачи состояла в следующем:
Найти все доступные комбинаций предложений, полученных методом T9 (predictive text)
Вводные данные:
Файл input.txt, в котором описаны последовательности цифр, имитирующие пользовательский ввод:
48 26624637 843 476877 63 5388377 66 3224 74663 539 9484 2 3278 222377 3428466279 63 96737 48 56657 87 46 843 3428466279 255 96737 2677377663464 86 843 73783623 63 5397876537 263 673377 8436 29 373783629 63 873 2 26678837 47 2 776472662253 6224463 8428 73234837 46788 786737 263 62647852837 3282 263 77684337 688788 46 2 873385 367628 2 644486273 47 2 37326 8428 226 22873 2 787664 63428483 366846625 73776673 3766 843 7533737 897422559 3327 67 467767 746784263 47 26 22273842833 79626542 9748464 638463 8428 462732737 77333 67 2738489 63 9748464 27 26672733 86 2 667625 638463 63 9748464 2 52648243 843 7762377 63 9748464 46 746784263 47 225533 78366472749 843 8376 625664 47 622274662559 8733 86 73337 86 2 666 778273 732826453Файл dictionary.txt, в котором представлен список английских слов, который используется для предсказания заданного слова из последовательности выше.
Выходные данные:
Файл output.txt, в котором собраны все возможные варианты предложений.
Разбор задачи
Первое, что приходит на ум, так это использовать префиксные деревья. А перед этим стоит пояснить что же это такое.
Префиксное дерево — структура данных для хранения строк, построенная в виде дерева, где на ребрах записаны символы, а некоторые вершины помечены как конечные. Классически данная структура может быть представлена изображением ниже:
Префиксное дерево проще всего хранить в виде ссылок на вершины. Каждая вершина обычно содержит информацию о том, является ли она конечной, ссылки на связаные вершины, а также любая дополнительная информация, зависящая от задачи.
Для латинского алфавита префиксное дерево может быть реализовано по приниципу ниже.
Перед тем как реализововывать дерево, в начале нам понадобится определить карту соответствия букв цифрам в раскладке клавиатуры кнопочного телефона:
Маппинг
export const keyMap: Record<string, number> = { a: 2, b: 2, c: 2, d: 3, e: 3, f: 3, g: 4, h: 4, i: 4, j: 5, k: 5, l: 5, m: 6, n: 6, o: 6, p: 7, q: 7, r: 7, s: 7, t: 8, u: 8, v: 8, w: 9, x: 9, y: 9, z: 9, };Далее приступим к реализации непосредственно префиксного дерева. Для этих целей заведем класс 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();Код задачи доступен на гитхаб. Спасибо за внимание!
ссылка на оригинал статьи https://habr.com/ru/post/599029/
Добавить комментарий