多语言词典的数据结构？

Question

一句话总结：建议针对主要印欧语言（底部列出的语言列表）构建最优（查找速度/紧凑性）数据结构，以表示多语言词典。

假设您想构建一些数据结构来实现一个多语言词典，例如互联网上排名前N（N〜40）的欧洲语言，选择语言按照网页数量（问题底部给出了语言的粗略列表）。目标是存储每种语言的工作词汇（即英语的25,000个单词等），不包括专有名词。不确定是否存储复数形式、动词变位、前缀等，或者添加语言特定的规则，说明这些是如何从名词单数或动词词干形成的。此外，您可以选择如何编码和处理重音、双元音和语言特定的特殊字符，例如可能在可能的情况下将其转写（例如罗马化德语ß为'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。 -

我查看了SO（stackoverflow.com），虽然有相关的问题，但没有这个确切的问题。我不需要SQL数据库。可以参考一篇2000年的论文："Estimation of English and non-English Language Use on the WWW" - Grefenstette & Nioche。还有一个 多语言字典列表。 资源：两个在线多语言字典分别是Interglot（英/德/荷/法/西/瑞）和LookWayUp（英<->法/德/西/荷/葡）。

---

需要包含的语言：

为了简单起见，可能主要包括印欧语系：英语、法语、西班牙语、德语、意大利语、瑞典语+阿尔巴尼亚语、捷克语、丹麦语、荷兰语、爱沙尼亚语、芬兰语、匈牙利语、冰岛语、拉脱维亚语、立陶宛语、挪威语、波兰语、葡萄牙语、罗马尼亚语、俄语、塞尔维亚-克罗地亚语、斯洛伐克语、斯洛文尼亚语+布列塔尼语、加泰罗尼亚语、科西嘉语、世界语、盖尔语、威尔士语

可能包括俄语、斯拉夫语、土耳其语，排除阿拉伯语、希伯来语、伊朗语、印度语等。也许还可以包括马来语族。请告诉我可行性如何。

- smci

---

你处理本地化的单词吗？（"Localized" 是错误的拼写！） - Arafangion

我不知道，你有没有任何数字来说明他们如何增加词汇量？我们是在谈论同一个单词的变体（例如美式英语的-ize和英式英语的-ise），还是添加全新的单词？我只考虑工作词汇量（例如英语中的25,000个单词），而不是完整的词汇表。假设：在不影响构建N种语言的多语言结构的主要任务的前提下，尽可能地增加词汇量。 - smci

变体，这似乎是Mac OS X默认支持的类型。 - Arafangion

那不是对问题的回答，只是一条简单的评论，而且还是针对其他人的。现在，你所说的快是什么意思？多慢才算可以接受？1秒？10秒？0.01秒？它是否实际包含真正的定义，还是只有链接？与未压缩内容相比，它应该有多紧凑？ - Alexey Frunze

如果有人提交了一个（常见的）拼写错误，你的索引如何自动学习区分heroes（英雄的复数）和heros（三明治）？或者在法语中是héros？那么对于仅仅输入了外语单词但没有重音符号的外语使用者，我们如何避免错误地索引呢？ - smci

Answer 1

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

多语言词典是一个庞大而耗时的工程。您没有详细讨论您的词典的确切用途：很可能是统计，而不是翻译，也不是语法.....不同的用途需要收集不同的数据，例如将“went”分类为过去时态。

首先，在文档中制定您的第一个要求，并使用编程接口原型。对于复杂的业务逻辑，我经常看到在算法概念之前询问数据结构。那么就会开始错误，冒着feature creep的风险。或者是过早的优化，例如罗马化，可能没有任何优势，并且阻止了双向性。

也许你可以从一些活跃的项目开始，比如Reta Vortaro; 它的XML可能不够高效，但可以为你提供组织方面的一些想法。有几个学术语言项目。最相关的方面可能是词干处理：识别greet/greets/greeted/greeter/greeting/greetings (@smci)作为同一（主要）条目的一部分。你需要采用已经编程好的词干处理器；它们通常经过了充分测试，并已经应用于电子词典中。我的建议是在不浪费太多精力和动力的情况下研究这些项目；只需收集想法并看看它们可能在哪里使用即可。

我认为人们可以想出的数据结构是次要的。我会首先将所有内容收集到一个定义良好的数据库中，然后生成所使用的软件数据结构。然后您可以比较和衡量替代方案。对于开发人员来说，这可能是最有趣的部分，创建美丽的数据结构和算法。

---

一个答案

要求：

单词到[语言，定义参考]列表的映射。定义列表。

多个单词可以有相同的定义，因此需要定义参考。 定义可以由语言限定的定义（语法属性、词形变化）和/或语言无关的定义（概念描述）组成。

一个单词可以有多个定义（书=（名词）阅读材料，=（动词）预订位置使用）。

备注

由于处理的是单个单词，因此不考虑出现的文本通常是单语的。由于文本可能是混合语言的，并且我在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;
}

具体的数据结构：

单词定义最好使用优化的哈希映射。

---

请允许我补充：

最终我想出了一个具体的数据结构。我从以下内容开始。

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

- Joop Eggen

---

Joop，挑战仅在于1）快速识别一个单词在哪些语言中是合法的，以及2）返回指向这些定义的指针集。假设您从N个单独的字典（如Reta Vortaro）开始。我没有具体应用的想法，我只是想概述这个概念上如何实现。可以将其视为类似于Google面试问题的思考题。 - smci

对于 flambé，英语词干可以指向法语单词（然后您还需要具有语言中立的定义结构，或者 DefinitionEntry 可能包含 (语言、定义) 对的列表）？将会有一些通用的外来词，比如 pizza，它们在大多数/所有 N 种语言中都是合法的。我猜您进一步开发的方式取决于 Definition 对象的确切含义（特定于语言的定义？语言中立的定义？特定于语言的同义词列表？...） - smci

关于词干提取器。以荷兰语单词 investering 为例，英语的词干提取器会寻找 invester 并且无法进一步处理。 - Joop Eggen

@JoopEggen 你知道我在哪里可以下载一个类似于中英文词典（https://cc-cedict.org/wiki/）的西班牙语 - 英语词典吗？ - user3871

@Growler 抱歉，但至少那些是流行的编程语言。祝你好运。 - Joop Eggen

Answer 2

我不确定这个方法是否适用于您的特定问题，但这里有一个思路可以考虑。

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

由于不同的语言使用不同的字母表，因此将每种语言按字母表分开以便尽可能地减小自动机的转换表大小可能是个好主意。毕竟，如果您有使用拉丁和西里尔字母的单词，那么代表希腊单词的状态转换可能全部指向拉丁字母的死状态，而带有拉丁字母的希腊字符的单词的希腊字符的转换也会指向死状态。因此，对于每个字母表有多个自动机，这样可以消除大量的浪费空间。

- templatetypedef

---

我其实不确定最好的做法是什么。我的第一反应是将带有重音的基本拉丁字母与希腊字母和西里尔字母分开处理，但我真的不知道这是否是一个好主意。我没有多少处理多种语言的经验，所以也许这显然是个糟糕的选择，罗马化可能是个好主意。 - templatetypedef

你的意思是要为N种语言使用N种数据结构吗？那太大了。至少合并主要的罗曼语系语言（法语、西班牙语、葡萄牙语，也许还有意大利语）是可能的吧？ - smci

不，你一定希望将大多数罗曼语言合并在一起！我主要是指按字母表分类，以避免在每个表中有大量浪费的空间。 - templatetypedef

请告诉我，我给出的语言列表大约有多少个字母？特别是当您合并语言时，您需要告诉我如何处理变音符号。西班牙语和葡萄牙语使用波浪符（tilde）表示不同的含义，而法语根本没有；如何避免添加约20个额外的带重音字符？ - smci

@templatetypedef 让我们在聊天中继续讨论。 - smci

Answer 3

在自然语言处理领域中，常见的解决方案是有限状态自动机。请参阅http://www.stanford.edu/~laurik/fsmbook/home.html。

- bmargulies

---

链接页面不是很清晰。这是什么意思？ - Suragch

Answer 4

简单。

为您的数据（所有字典的联合）构建一个最小完美哈希函数（离线构建哈希），并享受O(1)查找，直到永远。

利用您的键是静态已知的事实。不关心您的重音符号等（如果需要，请在哈希之前对它们进行规范化）。

- Don Stewart

---

不，这并没有涉及语言之间的紧凑性或重叠。"Man, mankind, manhole, mangiare, Mannschaft..." - smci

你还没有完成第二部分：你还必须返回每种语言中相应定义的指针。挑战不仅是为N=40种语言哈希大量布尔值，任何人都可以做到。您想要增加存储事物的效率，以便您不需要为每个动词变形或名词复数使用指针。在英语中，greet/greets/greeted/greeter/greeting/greetings 应该使用相同的指针。现在如何将这种结构推广到其他语言？ - smci

Answer 5

我有一个类似（但不完全相同）的任务：为集合实现四向映射，例如A、B、C、D。

每个项目x在所有集合中都有它的投影，x.A、x.B、x.C、x.D；

任务是：对于遇到的每个项目，确定它属于哪个集合，并找到它在其他集合中的投影。

使用语言类比：对于任何单词，识别它的语言并找到所有其他语言的翻译。

然而：在我的情况下，一个单词可以被唯一地识别为仅属于一种语言，因此没有假朋友，例如西班牙语中的burro是英语中的驴子，而意大利语中的burro是英语中的黄油（另请参见https://www.daytranslations.com/blog/different-meanings/）

我实现了以下解决方案：

• 四个映射/字典将条目与其唯一ID（整数）匹配

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

• 四个映射/字典将唯一ID与相应的语言匹配

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

对于每个遇到的 x，我需要进行最多 4 次搜索才能获取其 id（每次搜索为 O(log(N))）；然后是 3 次访问操作，每次为 O(log(N))。总体而言，为 O(log(N))。

我尚未实现此功能，但我不明白为什么哈希集不能用于任何一组字典，使其成为 O(1)。

回到您的问题： 给定 M 种语言中的 N 个概念（因此总共有 N*M 个单词）

我的方法如下：

M 个查找哈希集，为每种语言提供整数 id（如果该单词不存在于该语言中，则为 None/null）。 重叠情况由于不同语言的查找将产生不同的 id 而得以解决。

对于每个单词，您需要在对应于语言的哈希集中进行 M*O(1) 次查找，得到 K<=M 个 id，标识该单词属于 K 种语言；

对于每个 id，您需要在实际字典中进行 (M-1)*O(1) 次查找，将 K 个 id 映射到 M-1 个翻译中的每个翻译。

总的来说，O(MKM)的时间复杂度还不错，考虑到你的M=40，而且在大多数情况下K都比M小得多（对于相当多的单词来说，K=1）。

至于存储方面：NM个单词+ NM个整数用于id-to-word字典，同样数量的存储用于反向查找（word-to-id）；

- OverInflatedWalrus

---

我不认为这与我的问题有关，而且你的前提“在我的情况下，一个单词只能被唯一地标识为属于一种语言”是完全人为的，并违反了问题（因此，“跨语言的唯一整数ID”立即被排除），但无论如何，你还没有解决如何处理“burro”（西班牙语）、“burrito”（西班牙语和英语）、“burrow”（英语）等单个数据结构的问题。 “保持N个单独的哈希/字典，每种语言一个”将违反我给出的两个约束条件，既会浪费大量内存，又会查找速度较慢。 - smci

请提供需要翻译的具体内容。 - OverInflatedWalrus