Tengo una cadena S y una lista de cadenas allItems , allItems contiene cadenas que pueden tener "subpalabras" comunes pero un elemento nunca es una extensión de otro:
//good, they both contain Fuzzy but Fuzzy isn't in allItems const allItems = "FuzzyBunny", "FuzzyBear" //not good BCS allItems[i] = whatever1+allItems[j]+whatever2 const allItems = "Fuzzy", "FuzzyBear", "FuzzyBunny" , "FuzzyBearBunny" Mi objetivo es encontrar cada coincidencia o coincidencia aproximada de una cadena en todos los allItems en S junto con su índice (puede ser el inicio o el final, o idealmente ambos). He estado buscando algunos algoritmos para hacer esto, similar al algoritmo aho-corasick, pero eso no hace una coincidencia aproximada de cadenas.
Ejemplo:
S = "I love FuzzyBears and FuzzyDucks" allItems = ["FuzzyBear", "FuzzyDuck"]->
[ { match: "FuzzyBear", matchIndex: 0, startIndex: 7, endIndex: 16 }, { match: "FuzzyDuck", matchIndex: 1, startIndex: 22, endIndex: 31 } ]Todavía soy bastante nuevo en la coincidencia de patrones, por lo que agradecería algunos recursos sobre cómo codificar cualquiera de los algoritmos recomendados.
ACTUALIZACIÓN: Encontré un autómata Fuzzified Aho-Corasick como se describe aquí , pero tengo muy poca idea de cómo implementar esto en JS. Tampoco tengo problemas con el código lento ya que lo uso para una sola ejecución, y rara vez necesita hacer esto a menudo.
import difflib s = "I love FuzzyBears and FuzzyDucks" allitems = ["FuzzyBear", "FuzzyDuck"] lst = [] for x in allitems: d = {} match = difflib.get_close_matches(x, s.split()) if match: d["match"] = x d["matchIndex"] = allitems.index(x) d["startIndex"] = s.find(x) d["endIndex"] = d["startIndex"] + len(x) lst.append(d) print(lst) >>> [{'match': 'FuzzyBear', 'matchIndex': 0, 'startIndex': 7, 'endIndex': 16}, {'match': 'FuzzyDuck', 'matchIndex': 1, 'startIndex': 22, 'endIndex': 31}] import difflib from itertools import combinations s = "I love FuzzyBears and FuzzyDucks" allitems = ["FuzzyBear", "FuzzyDuck"] lst = [] for x in allitems: d = {} match = difflib.get_close_matches(x, [x[i:j] for i, j in combinations(range(len(x) + 1), r=2)]) if match: d["match"] = x d["matchIndex"] = allitems.index(x) d["startIndex"] = s.find(x) d["endIndex"] = d["startIndex"] + len(x) lst.append(d) print(lst) >>> [{'match': 'FuzzyBear', 'matchIndex': 0, 'startIndex': 7, 'endIndex': 16}, {'match': 'FuzzyDuck', 'matchIndex': 1, 'startIndex': 22, 'endIndex': 31}]Después de un montón de búsqueda en línea:
const s = "I love FuzzyBears and FuzzyDucks"; const allitems = ["FuzzyBear", "FuzzyDuck"]; const lst = []; for (const i of allitems) { const x = {}; if (s.includes(i)) { x["match"] = i; x["matchIndex"] = allitems.indexOf(i); x["startIndex"] = s.indexOf(i); x["endIndex"] = s.indexOf(i) + i.length; } lst.push(x); } console.log(lst); >>> [ { match: 'FuzzyBear', matchIndex: 0, startIndex: 7, endIndex: 16 }, { match: 'FuzzyDuck', matchIndex: 1, startIndex: 22, endIndex: 31 } ]