将具有多个拼写的单词映射到关键字列表的最佳方法？

Question

我有一堆可变拼写的ngram，我想将每个ngram映射到已知期望输出列表中的最佳匹配词。你知道吗

例如，['mob'、'mob'、'mobi'、'MOBIL'、'Mobile]映射到所需的'Mobile'输出。你知道吗

['desk'、'desk+Tab'、'Tab+desk'、'Desktop'、'dsk']的每个输入都映射到所需的'Desktop'输出

我有大约30个这样的“输出”字，和一堆大约几百万个ngram（更少的是唯一的）。你知道吗

我目前的最佳想法是获取所有唯一的ngram，将其复制并粘贴到Excel中，然后手动构建一个映射表，耗时太长而且不可扩展。 第二个想法是模糊匹配，但不匹配。你知道吗

我在自然语言术语或库方面根本没有经验，所以我找不到一个答案，当唯一ngram的数量增加或“输出”单词发生变化时，如何更好、更快和更广泛地实现这一点。你知道吗

有什么建议吗？你知道吗

Answer 1

经典的方法是，为每个ngram建立一个“特征矩阵”。每个单词映射到一个输出，该输出是介于0和29之间的分类值（每个类对应一个）

例如，特征可以是fuzzy-wuzzy给出的余弦相似性，但通常需要更多。然后根据创建的特征训练分类模型。这个模型通常可以是任何东西，一个神经网络，一个增强的树，等等

Answer 2

因为你只有大约30个类，你可以确定一个距离度量，比如说在单个单词的情况下Levenshtein distance，然后给每个ngram分配它最近的类。你知道吗

这样就不需要存储大量的内存。你知道吗

（如果ngram是整个数组，则可以平均数组中每个元素之间的距离）。你知道吗

Answer 3

其思想是使用前缀树来构建映射的字典 从你的单字到它最大的独特超级字符串。一旦我们建立了这个，对于超弦与单词本身相同的单词，我们尝试对列表中最接近的单词进行模糊匹配，并返回其超弦。所以“dsk”会发现“des”或“desk”是最接近的，我们提取它的超弦。你知道吗

import org.apache.commons.collections4.Trie;
import org.apache.commons.collections4.trie.PatriciaTrie;

import java.util.*;
import java.util.SortedMap;

public class Test {

    static Trie trie = new PatriciaTrie<>();

    public static int cost(char a, char b) {
        return a == b ? 0 : 1;
    }

    public static int min(int... numbers) {
        return Arrays.stream(numbers).min().orElse(Integer.MAX_VALUE);
    }

    // this function taken from https://www.baeldung.com/java-levenshtein-distance
    static int editDistance(String x, String y) {
        int[][] dp = new int[x.length() + 1][y.length() + 1];

        for (int i = 0; i <= x.length(); i++) {
            for (int j = 0; j <= y.length(); j++) {
                if (i == 0) {
                    dp[i][j] = j;
                } else if (j == 0) {
                    dp[i][j] = i;
                } else {
                    dp[i][j] = min(dp[i - 1][j - 1] + cost(x.charAt(i - 1), y.charAt(j - 1)), dp[i - 1][j] + 1,
                            dp[i][j - 1] + 1);
                }
            }
        }

        return dp[x.length()][y.length()];
    }

    /*
     * custom dictionary that map word to its biggest super string.
     *  mob -> mobile,  mobi -> mobile,  desk -> desktop
     */
    static void initMyDictionary(List<String> myList) {

        for (String word : myList) {
            trie.put(word.toLowerCase(), "0"); // putting 0 as default
        }

        for (String word : myList) {

            SortedMap<String, String> prefixMap = trie.prefixMap(word);

            String bigSuperString = "";

            for (Map.Entry<String, String> m : prefixMap.entrySet()) {
                int max = 0;
                if (m.getKey().length() > max) {
                    max = m.getKey().length();
                    bigSuperString = m.getKey();
                }
                // System.out.println(bigString + " big");
            }

            for (Map.Entry<String, String> m : prefixMap.entrySet()) {
                m.setValue(bigSuperString);
                // System.out.println(m.getKey() + " - " + m.getValue());
            }
        }

    }

    /*
     * find closest words for a given String.
     */
    static List<String> findClosest(String q, List<String> myList) {

        List<String> res = new ArrayList();
        for (String w : myList) {
            if (editDistance(q, w) == 1) // just one char apart edit distance
                res.add(w);
        }
        return res;

    }

    public static void main(String[] args) {

        List<String> myList = new ArrayList<>(
                Arrays.asList("mob", "MOB", "mobi", "mobil", "mobile", "desk", "desktop", "dsk"));

        initMyDictionary(myList); // build my custom dictionary using prefix tree

        // String query = "mob"
        // String query = "mobile";
        // String query = "des";
        String query = "dsk";

        // if the word and its superstring are the same, then we try to find the closest
        // words from list and lookup the superstring in the dictionary.
        if (query.equals(trie.get(query.toLowerCase()))) {
            for (String w : findClosest(query, myList)) { // try to resolve the ambiguity here if there are multiple closest words
                System.out.println(query + " -fuzzy maps to-> " + trie.get(w));
            }

        } else {
            System.out.println(query + " -maps to-> " + trie.get(query));
        }

    }

}