构建一个由一百万个单词组成的后缀树，并使用测试集对其进行查询，以找到最接近的匹配并进行分类
我试图解决的问题是:我有一百万个单词(多种语言)和一些类别，它们被归类为我的训练语料库。给定单词的测试语料库(数量肯定会随着时间的推移而增加)，我希望在训练语料库中获得这些单词中每个单词的最接近匹配，从而将该单词归类为其最接近匹配的相应类别。
我的解决方案是:最初，我做了这种没有规模的蛮力。现在，我想在训练语料库(O(n))的连接上构建一个后缀树，并查询测试语料库(固定时间)。尝试用python来做这件事。
我正在寻找工具或包，以帮助我开始，或者寻找其他更有效的方法来解决手头的问题。提前谢谢。
编辑1:至于如何找到最接近的匹配，我考虑的是精确匹配对齐的组合(从后缀树中)，然后对于剩余的输入字符串部分，我考虑使用仿射间隙惩罚函数进行局部对齐。
回答 1
Stack Overflow用户
发布于 2019-06-26 01:34:19
对于最接近的匹配，您使用什么距离度量？
有一些论文介绍了如何使用后缀树进行编辑距离搜索。对于每个后缀，存在编辑矩阵的扩展，并且可以对论文进行排序，以便让人们对后缀树进行排名搜索，以按距离递增的顺序找到匹配的项目。
一个这样的例子是具有编辑距离约束的Top-k字符串相似性搜索(2013) https://doi.org/10.1109/ICDE.2013.6544886 https://scholar.google.com/scholar?cluster=13387662751776693983
提出的解决方案避免了在添加列时计算表中的所有条目。
在您的问题中，似乎每个单词都有适用于它们的类，如果它们不依赖于上下文，那么上面的方法就可以工作，一个单词到类的映射就足够了。但如果它们依赖于上下文，那么这似乎更接近于词性标注。
https://stackoverflow.com/questions/56758408
复制相似问题