2

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

例如，['mob', 'MOB', 'mobi', 'MOBIL', 'Mobile] 映射到“mobile”的期望输出。

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

我有大约 30 个这样的“输出”单词，还有一堆大约几百万个 ngram（独特的少得多）。

我目前最好的想法是获取所有唯一的 ngram，将其复制并粘贴到 Excel 中并手动构建映射表，耗时太长且不可扩展。第二个想法是模糊（fuzzy-wuzzy）匹配，但匹配得不是很好。

我在自然语言术语或库方面完全没有经验，因此当唯一 ngram 的数量增加或“输出”单词发生变化时，我无法找到如何更好、更快、更可扩展地完成这项工作的答案。

有什么建议吗？

4

3 回答 3

1

这个想法是使用前缀树来构建一个字典，将列表中的单词映射到其最大的唯一超级字符串。一旦我们构建了这个，对于超字符串与单词本身相同的单词，我们尝试对列表中最接近的单词进行模糊匹配并返回其超字符串。所以“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));
        }

    }

}
于 2019-02-02T21:05:05.990 回答
1

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

例如，特征可以是由模糊模糊给出的余弦相似度，但通常您需要更多。然后根据创建的特征训练分类模型。该模型通常可以是任何东西，神经网络、增强树等。

于 2019-02-02T08:29:27.067 回答
1

由于您只有大约 30 个类，您可以确定一个距离度量，例如在单个单词的情况下说Levenshtein 距离，并为每个 ngram 分配它最接近的类。

这样就不需要存储整个 lotta ngrams。

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

于 2019-02-02T08:29:53.567 回答