Come viene implementata la ricerca fuzzy per i percorsi dei file

Supponiamo di avere percorsi di file come questo:

my/long/directory/structure/index.js
my/long/directory/structure2/index.js
my/long/directory/structure3/index.js
my/long/directory/structure.../index.js
my/long/directory/structuren/index.js
my/long/directory/index.js
my/long/directory2/index.js
my/long/directory.../index.js
my/long/directoryn/index.js
my/long/index.js
my/index.js
...

Cerco d <n> i (ad esempio d 2 i o d 3 i ) e restituisce questo:

my/long/d̲irectory/structuren̲/i̲ndex.js
my/long/d̲irectoryn̲/i̲ndex.js

Le domande sono 2:

1. In che modo corrisponde effettivamente alle stringhe.
2. Come restituisce i risultati come evidenziato dalla sintassi.

Per (1), c'è la struttura dati e l'algoritmo . In termini di struttura dei dati, ho visto molte funzionalità simili a quelle di autocomplete raccomandate per essere implementate come un trie. Questo ha senso per le parole chiave, ma non vedo come funzionerebbe per un percorso di file. Come prima cosa, sembra che potresti suddividerlo in singole directory / nomi di file:

my
long
directory
structuren
index.js

E avere un trie per ogni livello. Ciò consentirebbe almeno per corrispondenza prefisso esatto del percorso del file. Non vedo come potrebbe funzionare per la corrispondenza fuzzy, come in una ricerca d <n> i . Quella ricerca si estende su diversi livelli di questo sistema multi-trie. L'unico modo in cui posso vederlo restituire risultati sfocati è controllare ogni percorso del file dall'inizio alla fine , quindi non meglio di una semplice regexp match su ogni percorso del file nella sua interezza. Quindi mi chiedo quale tipo di struttura dati sia effettivamente utilizzata per la corrispondenza fuzzy in questo caso.

Per (2), la maggior parte delle implementazioni di fuzzy che ho visto si basano sulla distanza di levenshtein e restituiscono semplicemente una corrispondenza sì / no, non un albero di analisi. Ti chiedi se ci sono implementazioni che restituiscono l'albero di analisi, o ci sono modi alternativi per farlo. In questo modo puoi sintassi facilmente evidenziare senza dover ricorrere a un hack che duplica parte del lavoro di trovare le parti corrispondenti del testo del file dal frontend.