Структура данных для многоязычного словаря?

Ответ 1

Я не буду выигрывать здесь, но некоторые вещи.

Многоязычный словарь - это большая и трудоемкая задача. Вы не говорили подробно о точном использовании, для которого предназначен ваш словарь: статистический, вероятно, не переводческий, а не грамматический,... Различные способы использования требуют сбора разных данных, например, классификация "пошла" как прошедшее время.

Сначала сформулируйте свои первые требования в документе и с прототипом запрограммированного интерфейса. Задавая структуры данных перед алгоритмической концепцией, я часто вижу сложную бизнес-логику. Тогда можно было бы ошибиться, рискуя функцией ползучести. Или преждевременная оптимизация, такая как руманизация, которая может не иметь никакого преимущества, и барботоспособность.

Возможно, вы можете начать с некоторых активных проектов, таких как Reta Vortaro; его XML может быть неэффективным, но дать вам несколько идей для организации. Существует несколько академических лингвистических проектов. Наиболее важным аспектом может быть stem: распознавание приветствия/приветствия/приветствия/приветствия/приветствия/приветствия (@smci) как принадлежащих к одной и той же (основной) записи. Вы хотите взять уже запрограммированных стволовых; они часто хорошо тестируются и уже применяются в электронных словарях. Я бы посоветовал исследовать эти проекты, не теряя при этом много энергии, стимула к ним; достаточно, чтобы собирать идеи и видеть, где они могут быть использованы.

Структуры данных, которые можно придумать, являются ИМХО второстепенной важности. Я бы сначала собирал все в хорошо определенной базе данных, а затем генерировал программное обеспечение, используемое структурами данных. Затем вы можете сравнить и измерить альтернативы. И это может быть для разработчика самой интересной частью, создавая красивую структуру данных и алгоритм.

Ответ

Требования:

Карта слова в список [язык, определение ссылки]. Список определений.

Несколько слов могут иметь одно и то же определение, отсюда и необходимость ссылки на определение. Определение может состоять из определения, связанного с языком (грамматические свойства, declinations), и/или языкового независимого определения (описания понятия).

Одно слово может иметь несколько определений (book = (существительное), чтение материала, = (глагол) зарезервировать использование местоположения).

Примечания

Как обрабатываются отдельные слова, это не учитывает, что существующий текст в целом моноязычен. Поскольку текст может быть смешанных языков, и я не вижу особых накладных расходов в O-сложности, которые кажутся несущественными.

Таким образом, общая абстрактная структура данных будет:

Map<String /*Word*/, List<DefinitionEntry>> wordDefinitions;
Map<String /*Language/Locale/""*/, List<Definition>> definitions;

class Definition {
    String content;
}

class DefinitionEntry {
    String language;
    Ref<Definition> definition;
}

Конкретная структура данных:

СловоDefinitions лучше всего обслуживается с оптимизированной картой хэша.

Позвольте мне добавить:

Наконец-то я создал конкретную структуру данных. Я начал со следующего.

Guava MultiMap - это то, что у нас есть, но Trove коллекции с примитивными типами - это то, что нужно, если использовать компактное двоичное представление в ядре.

Можно было бы сделать что-то вроде:

import gnu.trove.map.*;

/**
 * Map of word to DefinitionEntry.
 * Key: word.
 * Value: offset in byte array wordDefinitionEntries,
 * 0 serves as null, which implies a dummy byte (data version?)
 * in the byte arrary at [0].
 */
TObjectIntMap<String> wordDefinitions = TObjectIntHashMap<String>();
byte[] wordDefinitionEntries = new byte[...]; // Actually read from file.

void walkEntries(String word) {
    int value = wordDefinitions.get(word);
    if (value == 0)
        return;
    DataInputStream in = new DataInputStream(
        new ByteArrayInputStream(wordDefinitionEntries));
    in.skipBytes(value);
    int entriesCount = in.readShort();
    for (int entryno = 0; entryno < entriesCount; ++entryno) {
        int language = in.readByte();
        walkDefinition(in, language); // Index to readUTF8 or gzipped bytes.
    }
}

Ответ 2

Я не уверен, будет ли это работать для вашей конкретной проблемы, но здесь есть одна идея подумать.

Структура данных, которая часто используется для быстрых, компактных представлений языка, представляет собой DFA минимального состояния для языка. Вы можете построить это, создав trie для языка (который сам по себе является автоматом для распознавания строк в языке), а затем использует канонические алгоритмы для построения DFA для языка с минимальным состоянием. Для этого может потребоваться огромное количество времени предварительной обработки, но как только вы построите автомат, вы получите чрезвычайно быстрый поиск слов. Вы только начинаете в начальном состоянии и следуете помеченным переходам для каждой из букв. Каждое состояние может кодировать (возможно) 40-битное кодирование значения для каждого языка независимо от того, соответствует ли оно слову на этом языке.

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

Ответ 3

Общим решением этого в области НЛП являются конечные автоматы. См. http://www.stanford.edu/~laurik/fsmbook/home.html.

Ответ 4

Легко.

Построить минимальную совершенную хеш-функцию для ваших данных (объединение всех словарей, построение хеша в автономном режиме) и наслаждаться O (1) поиском для остальной части вечности.

Воспользовавшись тем, что ваши ключи известны статически. Не волнует ваши акценты и т.д. (Нормализуйте их до хэширования, если хотите).

Ответ 5

У меня была похожая (но не совсем) задача: реализовать четырехстороннее сопоставление для множеств, например A, B, C, D

Каждый элемент x имеет свои проекции во всех наборах, x.A, x.B, x.C, x.D;

Задача заключалась в следующем: для каждого обнаруженного элемента определить, к какому набору он относится и найти его проекции в других наборах.

Используя аналогию с языками: для любого слова определите его язык и найдите все переводы на другие языки.

Однако: в моем случае слово может быть однозначно идентифицировано как принадлежащее только одному языку, поэтому никакие фальшивые друзья, такие как burro на испанском языке, не являются ослами на английском языке, в то время как burro на итальянском языке является маслом на английском языке (см. также https://www.daytranslations.com/blog/different-meanings/)

Я реализовал следующее решение:

• Четыре карты/словари, соответствующие записи с ее уникальным идентификатором (целое число)

  AtoI[x.A] = BtoI[x.B] = CtoI[x.C] = DtoI[x.D] = i
  

• Четыре карты/словари, соответствующие уникальному идентификатору на соответствующем языке

  ItoA[i] = x.A;
  ItoB[i] = x.B;
  ItoC[i] = x.C;
  ItoD[i] = x.D;
  

Для каждого столкновения x мне нужно выполнить 4 поиска в худшем случае, чтобы получить его идентификатор (каждый поиск - O(log(N))); затем 3 операции доступа, каждая O(log(N)). В общем, O(log(N)).

Я не реализовал это, но я не понимаю, почему наборы хешей нельзя использовать ни для одного из наборов словарей, чтобы сделать это O(1).

Возвращаясь к вашей проблеме: Учитывая N понятий на M языках (всего N * M слов)

Мой подход адаптируется следующим образом:

M lookup hashsets, которые дают вам целочисленный идентификатор для каждого языка (или None/null, если слово не существует в языке). Перекрытый случай объясняется тем, что поиск по разным языкам даст разные идентификаторы.

Для каждого слова вы выполняете M * O (1) поиск в наборах хеш-кодов, соответствующих языкам, что приводит к идентификаторам K & lt; = M, идентифицирующим слово как принадлежащее языкам K;

для каждого идентификатора вам нужно выполнить (M-1) * O (1) поиск в реальных словарях, сопоставляя K-id с переводами M-1 каждый)

В общем, O (MKM), который я считаю неплохим, учитывая, что ваши M = 40 и K в большинстве случаев будут намного меньше, чем M (K = 1 для довольно большого количества слов).

Что касается хранения: слова NM + целые числа NM для словарей от слова к слову и столько же для обратного поиска (от слова к слову);