J'ai une pile de ngrammes d'orthographe variable, et je veux mapper chaque ngram à son meilleur mot correspondant à partir d'une liste de sorties connues désirées.
Par exemple, ['mob', 'MOB', 'mobi', 'MOBIL', 'Mobile] correspond à une sortie souhaitée de' mobile '.
Chaque entrée de ['desk', 'Desk + Tab', 'Tab + Desk', 'Desktop', 'dsk'] correspond à une sortie souhaitée de 'desktop'
J'ai environ 30 de ces mots de "sortie" et une pile d'environ quelques millions de ngrammes (beaucoup moins uniques).
Ma meilleure idée actuelle était d'obtenir tous les ngrammes uniques, de les copier et de les coller dans Excel et de créer manuellement une table de mappage, cela prenait trop de temps et n'était pas extensible. La deuxième idée était quelque chose avec une correspondance floue (floue-wuzzy) mais cela ne correspondait pas bien.
Je n'ai pas du tout d'expérience dans la terminologie ou les bibliothèques de langage naturel, donc je ne trouve pas de réponse à la manière dont cela pourrait être fait mieux, plus rapidement et de manière plus extensible lorsque le nombre de ngrammes uniques augmente ou que les mots de sortie changent.
Un conseil?
3 Réponses :
L'approche classique serait de construire une "matrice de fonctionnalités" pour chaque ngram. Chaque mot correspond à une sortie qui est une valeur catégorielle entre 0 et 29 (un pour chaque classe)
Les caractéristiques peuvent par exemple être la similarité cosinus donnée par floue wuzzy mais en général vous en avez besoin de beaucoup plus. Ensuite, vous entraînez un modèle de classification basé sur les fonctionnalités créées. Ce modèle peut généralement être n'importe quoi, un réseau de neurones, un arbre boosté, etc.
Comme vous n'avez qu'environ 30 classes, vous pouvez simplement déterminer une métrique de distance, comme par exemple Distance de Levenshtein dans le cas de mots simples, et attribuez à chaque ngram la classe dont il est le plus proche.
De cette façon, pas besoin de stocker un tas de ngrammes.
(Si le ngram est le tableau entier, peut-être faire la moyenne de la distance entre chaque élément du tableau).
L'idée est d'utiliser une arborescence de préfixes pour construire un dictionnaire qui mappe mot de votre liste à sa plus grande super-chaîne unique. une fois que nous avons construit cela, pour les mots dont la superstring est identique au mot lui-même, nous essayons de faire une correspondance floue des mots les plus proches de la liste et de renvoyer sa superstring. donc "dsk" trouverait "des" ou "desk" comme étant le plus proche et nous en extrayons la superstring.
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));
}
}
}
Pour clarifier, chaque ngram est-il un tableau comme `['mob', 'MOB', 'mobi', 'MOBIL', 'Mobile']` ou juste le mot 'Mobile'? Vous cherchez aussi à économiser de la mémoire ou à gagner en vitesse?