smc*_*mci 10 multilingual dictionary data-structures
单行摘要:建议主要代表印欧语系的多语言词典的最佳(查找速度/紧凑性)数据结构(在下面列出).
假设你想构建一些数据结构来实现一个多语言字典,比如说互联网上的前N(N~40)个欧洲语言,按网页数量排列语言选择(给出粗略的语言列表)在这个问题的底部).目的是存储每种语言的工作词汇(即英语等25,000个单词).排除正确的名词.不确定我们是否存储复数,动词变形,前缀等,或者添加关于如何从名词单词或动词词干形成这些词语的特定语言规则.您还可以选择我们如何编码和处理重音符号,双元音和特定语言的特殊字符,例如,在可能的情况下,我们可以音译(例如,将 德语Roman 罗马化为 's',然后添加规则进行转换).显然,如果你选择使用40-100个字符和一个trie,那么分支太多了,而且大多数都是空的.
任务定义:无论使用何种数据结构,都必须执行以下两项操作:
效率的主要指标是a)紧凑性(跨所有N种语言)和b)查找速度的权衡.插入时间并不重要.
所以:
(我检查了SO,并且有相关的问题,但没有这个确切的问题.当然不是在寻找一个SQL数据库.一篇2000篇论文可能有用:"估计WWW上的英语和非英语语言使用" - Grefenstette&Nioche和一个多语言词典列表)资源:两个在线多语言词典是Interglot(en/ge/nl/fr/sp/se)和LookWayUp(en < - > fr/ge/sp/nl/pt).
语言包括:
可能主要是印欧语言的简单:英语,法语,西班牙语,德语,意大利语,瑞典语+阿尔巴尼亚语,捷克语,丹麦语,荷兰语,爱沙尼亚语,芬兰语,匈牙利语,冰岛语,拉脱维亚语,立陶宛语,挪威语,波兰语,葡萄牙语,罗马尼亚语,俄语,塞尔维亚克罗地亚,斯洛伐克,斯洛文尼亚+布列塔尼,加泰罗尼亚,科西嘉,世界语,盖尔语,威尔士语
可能包括俄语,斯拉夫语,土耳其语,排除阿拉伯语,希伯来语,伊朗语,印度语等.也许包括马来语家庭.告诉我什么是可以实现的.
我不确定这是否适用于您的特定问题，但这是一个需要考虑的想法。
通常用于语言的快速、紧凑表示的数据结构是语言的最小状态 DFA。您可以通过为该语言创建一个特里树（它本身就是一个用于识别语言中的字符串的自动机）来构建它，然后使用规范算法为该语言构建一个最小状态 DFA。这可能需要大量的预处理时间，但是一旦您构建了自动机，您将可以非常快速地查找单词。您只需从开始状态开始，然后按照每个字母标记的转换即可。每个状态都可以为每种语言编码（也许）一个 40 位的值编码，无论该状态是否对应于该语言中的一个词。
因为不同的语言使用不同的字母表，所以最好按字母表将每种语言分开，这样您就可以最小化自动机的转换表的大小。毕竟，如果您有使用拉丁字母和西里尔字母的单词，则表示希腊单词的状态的状态转换可能都是拉丁字母上的死状态，而拉丁单词的希腊字符的状态转换也将是死状态. 因此，每个字母都有多个自动机可以消除大量浪费的空间。
我不会在这里赢得积分，但会赢得一些东西。
多语言词典是一项庞大且耗时的工作。您没有详细谈论您的字典的确切用途：可能是统计，不是翻译，不是语法，......不同的用法需要收集不同的数据，例如将“去”分类为通过时态。
首先在文档中制定您的第一个要求，并使用编程接口原型。我经常看到复杂的业务逻辑先问数据结构，然后再问算法概念。然后一开始就会出错，冒着功能蔓延的风险风险。或者过早的优化，比如罗马化，这可能没有任何优势，并且禁止双向性。
也许你可以从一些活跃的项目开始，比如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;
}
具体数据结构：
wordDefinitions 最好使用优化的哈希映射。
请让我补充一下：
我最终确实想出了一个具体的数据结构。我从以下几点开始。
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.
}
}