Привет, Хабр! На днях ко мне обратился ученик на одном из ресурсов, где я выступаю в качестве 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. Здесь вставка работает путем обхода дерева в соответствии со строкой, которая должна быть вставлена, а затем в суффикс строки добавляются новые узлы, не содержащиеся в дереве:

Код класса
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();

Код задачи доступен на гитхаб. Спасибо за внимание!

Комментарии (7)


  1. orekh
    01.01.2022 14:31
    +3

    А результат показать?


  1. aamonster
    01.01.2022 20:12

    А тут точно нужно заморачиваться с префиксными деревьями? Просто построить за один проход мультимап "пачка цифр –> слово" (на стандартных библиотечных мапах) – дёшево и сердито. И код получится легкочитаемым. А оптимизировать (если потребуется) уже потом (и тут уж понадобятся бенчмарки по процу и по памяти).


    1. dopusteam
      03.01.2022 10:22

      Нужно ж ещё по префиксам искать возможные варианты. Как это будет в Вашем случае реализовано?


      1. aamonster
        03.01.2022 13:50

        В смысле, на 26624637 вывести вначале подсказки на 2, потом на 26, потом на 266 и так далее?

        Или наоборот – для 26 вывести все слова, начинающиеся с соответствующих кнопок?


        1. dopusteam
          03.01.2022 14:04

          для 26 вывести все слова, начинающиеся с соответствующих кнопок?

          Вот это. Не все, ну часть хотя бы. Не помню, было ли такое в классическом Т9, но вроде было, по крайней мере в некоторых телефонах. Хотя оно может по другому называлось


          1. aamonster
            03.01.2022 14:35

            Это уже другая задача). Для неё и входные данные другие (нужны частоты слов, чтобы подсказки были осмысленными). Тут я базово тоже использовал бы мапу, но в неё клал бы не просто списки слов, а наборы слов с рейтингом (рейтинг – функция от избытка длины и от частоты слова), не допуская переполнения набора (при необходимости отбрасывая слова с самым низким рейтингом – возможно, для этого удобно будет хранить набор в виде бинарной кучи).

            Ну и тоже можно потом при необходимости мапу в префиксное дерево перевести...


  1. azatfr
    02.01.2022 12:20

    Ээээ не получится ли конфуз? Во времена кнопочных телефонов частенько получалось что т9 набирал не совсем то что нужно. lurkmore.to/T9