与多种拼写单词映射到的关键词列表的最佳方式？

Question

我有一堆的变量拼写的n-gram的，我想每个NGRAM映射到它的最佳匹配这个词称为理想的产出的清单。

例如，[“暴民”，“MOB”，“摩比”，“MOBIL”，“移动]映射到的期望输出‘移动’。

从[“桌子”，“桌子+ Tab键”，“Tab键+台”，“桌面”，“DSK”]每个输入映射到“桌面”的期望输出

我有近30种“产出”的话，和一堆约几百万的n-gram（少得多唯一的）。

我目前最好的办法是让所有的独特的n-gram，复制并粘贴到Excel和手工创建一个映射表，耗时过长，且不能扩展。第二个想法是相匹配的东西用模糊（模糊wuzzy），但它并没有匹配好。

在自然语言术语或图书馆在所有我没有经历过，所以我无法找到一个答案，这是如何做到更好，更快，更可延伸时的独特的n-gram增加或“输出”字的数量变化。

有什么建议？

Answer 1

经典的做法是，建立一个“功能列表”每个NGRAM。每个单词映射到一个输出，该输出0和29之间的分类值（每个类）

功能例如可以通过模糊wuzzy给出的余弦相似，但通常你需要更多。然后你训练基础上创建功能分类模型。这种模式通常可以是任何东西，一个神经网络，推进树等。

Answer 2

既然你只有约30个教学班，你可以只确定一个距离度量，好比说Levenshtein distance中的单个词的情况下，并指定每个统计ngram的类，它是最接近的。

这样，无需存储整个洛塔的n-gram。

（如果是的ngram整个阵列，也许平均跨越每个元件的距离阵列中）。

Answer 3

我们的想法是使用一个前缀树，以建立一个从你的清单映射词来其最大的独特的超弦的字典。一旦我们建立这一点，他们的话是超弦理论一样的单词本身，我们试图从列表中做的最接近词模糊匹配，并返回其超弦。所以“DSK”会发现“DES”或“服务台”是最接近我们提取其超弦。

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));
        }

    }

}