Ci sono alcune sottigliezze in questa domanda che non sono state ancora chiarite.
Tuttavia, ho un prototipo funzionante che sembra approssimare ciò che l'OP sta chiedendo.
Prima di descrivere il mio approccio, ecco un caso di test.
Per questo test case, l'elenco di parole è ottenuto da: link
(Dichiarazione di non responsabilità: i risultati dei motori di ricerca potrebbero contenere collegamenti a materiali protetti da copyright.)
Vengono applicati i seguenti criteri di filtro:
- Lunghezza almeno 4
- Tutte le lettere (nessuno spazio, trattino, apostrofi)
- Tutto in minuscolo (per saltare le inizializzazioni)
Quindi, a ogni parola univoca viene assegnato un numero intero, a partire da zero.
Per ogni parola, ne viene generata una piccola lista di modelli, sostituendo ogni volta un personaggio con un segnaposto. Ad esempio, dalla parola care verrà generato un elenco di 4 pattern:
?are
c?re
ca?e
car?
Ogni modello viene quindi utilizzato per cercare nuovamente l'elenco di parole. I colpi unici sono contati. Sottraendo uno da questo numero si ottiene il numero di amici per questa parola.
Ci sono altri aspetti che sono semplicemente ottimizzazioni delle prestazioni. Poiché l'ottimizzazione è principalmente un gusto personale, salterò i dettagli a meno che non ci sia un consenso sul fatto che dovrei includerli con la mia risposta.
Ho anche il codice sorgente C #, ma non so se dovrei pubblicarlo qui o meno, a meno che non ci sia un consenso.
Tra le classi C #, ne menzionerei due per la loro particolare utilità:
- Uno è una mappa bidirezionale tra una stringa e un valore intero assegnato sequenzialmente (che inizia con zero). In sostanza un
List<string> più un Dictionary<string, int> più una logica.
- Un'altra è una multi-mappa bidirezionale tra due serie di numeri interi da spazi dei nomi separati (Nota) . Questo è usato per memorizzare tuple di
(wordIndex, patternIndex) e consentire la ricerca usando uno dei due.
(Nota) dite, Tuple.Item1 significa indice di parole, Tuple.Item2 significa indice di pattern e dove la coincidenza di un indice di parole uguale a un indice di pattern è completamente irrilevante. (Ti prego, aiutami a migliorare questa descrizione.)
Primo caso di test: care dovrebbe restituire 22 corrispondenze, a sua volta incluse (quindi 21 amici veri)
care : 22
bare
cafe
cage
cake
came
cane
cape
card
care
carp
cart
case
cave
core
cure
dare
fare
hare
mare
pare
rare
ware
Secondo test case: butter dovrebbe restituire 10 corrispondenze, incluse di per sé (quindi 9 amici veri)
butter : 10
batter
better
bitter
buster
butler
butter
cutter
gutter
mutter
putter