多语言词典的数据结构？

Question

单行摘要：建议为主要代表印欧语的多语种词典提供最佳(查找速度/紧凑)数据结构(列表位于底部)。

假设您想要构建一些数据结构来实现一个多语言词典，比如互联网上的顶级N (N~40)欧洲语言，对语言的选择按网页数目分列 (这个问题的底部给出的语言粗略列表)进行排名。其目的是存储每种语言的工作词汇量(例如，25,000字的英语等)。不包括专有名词。不确定我们是储存复数、动词连词、前缀等，还是添加语言规则，说明它们是如何由名词单数或动词词干构成的。此外，您还可以选择如何编码和处理口音、diphthongs和特定于语言的特殊字符，例如，在可能的情况下，我们可以使用音译 things (例如，浪漫主义德语作为'ss'，然后添加一个规则来转换它)。显然，如果您选择使用40-100个字符和一个trie，有太多的分支，其中大多数是空的。

任务定义:无论使用什么数据结构，都必须同时执行以下两项操作：

1. 查找的主要操作是快速得到一个指示‘是的，这是一个有效的词在语言A，B和F，而不是C，D或E’。因此，如果N=40语言，您的结构很快返回40个布尔字母。
2. 次要操作是为每种语言(或无效时为null )返回该词的指针/对象(及其所有变体)。该指针/对象可以是用户定义的，例如词性部分和字典定义/词库明喻/翻译成其他语言的列表/.它可以是特定语言的，也可以是独立于语言的，例如，披萨的共享定义)

效率的主要衡量标准是a)紧凑性(跨越所有N种语言)和b)查找速度的权衡。插入时间不重要。紧凑性约束排除了内存浪费的方法，如“为每个单词保留单独的散列”或“为每种语言保留一个单独的散列，以及该语言中的每个单词”。

所以：

1. 可能的数据结构是什么，它们在查找速度/紧凑曲线上是如何排列的？
2. 你是否对所有N种语言都有统一的结构，或者把日耳曼语划分成一个子结构，把斯拉夫语划分成另一个子结构？或者只是N个单独的结构(这将允许你哈夫曼-编码)？
3. 您对字符、重音和特定于语言的特殊字符使用什么表示？
4. 理想情况下，给出算法或代码的链接(尤指链接)。Python或者其他的C -

(我查过了，有相关的问题，但没有这个问题。当然不是在寻找SQL数据库。一篇可能有用的2000年论文：“WWW上英语和非英语语言使用的估计”- Grefenstette和Nioche。资源:两个在线的多语言词典是Interglot (en/ge/nl/fr/sp/se)和LookWayUp (en<->fr/ge/sp/nl/pt)。

语文包括：

可能主要是印欧语：英语、法语、西班牙语、德语、意大利语、瑞典语+阿尔巴尼亚语、捷克语、丹麦语、荷兰语、爱沙尼亚语、芬兰语、匈牙利语、冰岛语、拉脱维亚语、立陶宛语、挪威语、波兰语、葡萄牙语、罗马尼亚语、俄语、塞尔维亚语、斯洛伐克语、斯洛文尼亚语+布雷顿语、加泰罗尼亚语、科西嘉语、世界语、盖尔语、威尔士语

可能包括俄语，斯拉夫语，土耳其语，不包括阿拉伯语，希伯来语，伊朗语，印度语等。告诉我什么是可以实现的。

Answer 1

我不会在这里赢分的，但是有些事情。

多语言词典是一项庞大而费时的工作.你没有详细说明你的字典的确切用途:统计可能，不是翻译，不是语法，.不同的用法要求收集不同的数据，例如，将“to”归类为传递时态。

首先，在文档中提出您的第一个需求，并使用一个编程的接口原型。在我经常看到的关于复杂业务逻辑的算法概念之前，询问数据结构。这样，一个人就会开始犯错，冒着特征蠕变的风险。或者是过早的优化，比如浪漫化，这可能没有任何优势，而且阻碍了竞争。

也许您可以从一些活动的项目(如雷塔·沃塔罗)开始；它的XML可能不是有效的，但是给您一些组织的想法。有几个学术的语言项目，。最相关的方面可能是greet/greets/greeted/greeter/greeting/greetings词干：将 (@smci)识别为属于同一(主要)条目。您想要使用已经编程的词干器；它们通常经过很好的测试，并且已经应用于电子词典中。我的建议是，在研究这些项目时，不要失去太多的精力、动力和动力；只需收集一些想法，看看它们可能被应用在哪里。

你能想到的数据结构，是次要的IMHO。我将首先收集一个定义良好的数据库中的所有数据，然后生成所使用的软件数据结构。然后，您可以比较和度量备选方案。对于开发人员来说，这可能是最有趣的部分，它创建了一个漂亮的数据结构&算法。

一个答案

Requirement:

从文字到语言列表的地图，定义参考。定义清单。

有几个词可以有相同的定义，因此需要一个定义参考。该定义可以由语言约束定义(语法属性、斜线)和/或语言索引定义(对概念的描述)组成。

一个词可以有几个定义(书=(名词)读物，=(动词)保留位置)。

备注

当单个单词被处理时，这并不认为出现的文本通常是单一语言的。由于文本可以是混合语言，而且我认为在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;
}

的具体数据结构：

优化后的哈希图为wordDefinitions提供了最佳服务。

，请允许我加上：

我终于想出了一个具体的数据结构。我从以下几个方面开始。

番石榴的MultiMap是我们这里所拥有的，但如果在核心中使用紧凑的二进制表示，则需要具有原始类型的宝物集合。

一个人会做这样的事情：

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.
    }
}

Answer 2

我不确定这是否对你的特殊问题有效，但有一个想法值得考虑。

通常用于快速、紧凑的语言表示的数据结构是该语言的最小状态DFA。您可以为该语言创建一个trie (它本身是识别语言中字符串的自动机)，然后使用规范算法为该语言构造一个最小状态DFA。这可能需要大量的预处理时间，但是一旦构建了自动机，您就可以非常快速地查找单词。您只需从开始状态开始，并为每个字母遵循标记的转换。每种状态都可以为每种语言编码(可能)40位值编码，无论状态是否对应于该语言中的一个单词。

因为不同的语言使用不同的字母表，所以最好将每种语言按字母表分开，这样就可以最小化自动机的转换表的大小。毕竟，如果你有使用拉丁字母和西里尔字母的单词，代表希腊语单词的国家的状态转换很可能都是拉丁字母上的死状态，而希腊语字符的拉丁字母转换也将是死状态。因此，每个字母都有多个自动机可以消除大量的浪费空间。

Answer 3

很简单。

为您的数据构建一个极小，完全散列函数 (所有字典的合并，离线构建散列)，以及永久的查找。

利用你的钥匙是静态已知的事实。不关心你的口音等等(如果你想的话，在散列之前将它们正常化)。