Лучший способ сопоставить слова с несколькими написаниями в списке ключевых слов?

Question

У меня есть куча нграмм переменной орфографии, и я хочу сопоставить каждую нграм со своим словом наилучшего соответствия из списка известных желаемых выходных данных.

Например, ['mob', 'MOB',' mobi ',' MOBIL ',' Mobile] сопоставляются с желаемым выходом 'mobile'.

Каждый вход от ['desk', 'Desk + Tab', 'Tab + Desk', 'Рабочий стол »,« dsk »] отображается на желаемый результат« рабочий стол »

У меня есть около 30 из этих« выходных »слов и куча около нескольких миллионов нграмм (гораздо меньше уникальных).

Моя лучшая идея на данный момент заключалась в том, чтобы получить все уникальные ngram, скопировать и вставить их в Excel и вручную создать таблицу сопоставления, это заняло слишком много времени и не было расширяемым.Второй идеей было что-то с нечетким (нечетким-нечетким) соответствием, но оно не очень хорошо соответствовало.

У меня совсем нет опыта работы с терминологией или библиотеками естественного языка, поэтому я не могу найти ответ на вопрос, как это можно сделать лучше, быстрее и эффективнее, когда число уникальных нграмм увеличивается или «выводится»слова меняются.

Есть совет?

Answer 1

Поскольку у вас есть только около 30 классов, вы можете просто определить метрику расстояния, например, скажем Расстояние Левенштейна в случае отдельных слов, и назначить каждой ngram класс, к которому она ближе всего.

Таким образом, нет необходимости хранить целые лотограммы.

(Если ngram - это целый массив, возможно, усредните расстояние между каждым элементом в массиве).

Answer 2

Идея состоит в том, чтобы использовать дерево префиксов для создания словаря, который отображает слово из вашего списка в его самую большую уникальную суперструну.как только мы построим это, для слов, суперструна которых совпадает с самим словом, мы пытаемся сделать нечеткое совпадение ближайших слов из списка и вернуть его суперструну.таким образом, «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));
        }

    }

}

Answer 3

Классический подход заключается в построении «Матрицы возможностей» для каждой нграммы.Каждое слово отображается в вывод, который является категориальным значением от 0 до 29 (по одному для каждого класса)

Примерами могут быть, например, косинусное сходство, задаваемое нечетким вузи, но обычно вам требуется гораздо больше.Затем вы тренируете модель классификации на основе созданных функций.Эта модель обычно может быть чем угодно, нейронной сетью, расширенным деревом и т. Д.