String Algoritmo di ricerca

3

Un titolo per un film può essere ambiguo. (Ad esempio Il Signore degli Anelli, Il Signore degli Anelli, Il Signore degli Anelli, Il) Esiste una voce di database con un elenco di titoli di film mappati su un identificativo univoco.

Sto provando a scrivere un metodo che prende un input di titolo String e restituisce l'identificatore univoco mappato ad esso dopo aver risolto qualsiasi ambiguità. (Is is a sequel? A remake?)

Che cos'è una buona struttura dati da usare qui?

    
posta Theheist1992 09.03.2015 - 18:27
fonte

2 risposte

3

La tua domanda è un po 'oscura in quanto il titolo richiede un algoritmo, ma chiedi anche una struttura dati. Descriverò quello che ho fatto con un problema simile, che riguarda la musica.

Il modo in cui mi sono avvicinato era con una serie di trasformazioni di stringhe che producevano una stringa con la massima ambiguità rimossa possibile.

Alcune regole:

  • Rimuovi tutti gli spazi
  • Cambia tutte le lettere non ASCII in equivalenti ASCII. (ö - > o)
  • Modifica tutto in maiuscolo
  • Se viene rilevata una virgola, scambia il lato destro del comune con la sinistra
  • Rimuovi parole comuni come "il", "di", ecc.
  • Modifica i numeri romani in arabo ("VII" - > 7)

Quindi mi troverei a:

Blue Öyster Cult -> BLUEOYSTERCULT
Amos, Tori -> TORIAMOS
The Red Hot Chili Peppers -> REDHOTCHILIPEPPERS

L'ho usato per tutti i confronti, anche se non è mai stato esposto all'utente. Nel mio caso, l'ho appena usato come identificativo.

Le regole erano necessariamente un mucchio di euristiche sviluppate sperimentando con veri dati CDDB . Ovviamente non era garantito che fosse infallibile, ma non era difficile trovare un set che funzionasse la maggior parte del tempo.

Il tuo problema non è lo stesso. Il remake sarà un problema perché i tuoi titoli corrisponderanno. Ciò potrebbe essere parzialmente risolvibile cercando date nel titolo ("Total Recall (2013)") ma sospetto che spesso manchino i dati.

    
risposta data 09.03.2015 - 18:51
fonte
2

Inizierei sanificando i dati di input come @Steven Burnap e poi calcola la distanza Levenshtein tra l'input e tutti i titoli di film conosciuti. Restituisci i migliori risultati della coppia. Poiché è probabile che ci sia un alto grado di variazione tra l'input dei tuoi utenti e il tuo elenco di titoli di film noti, un algoritmo di ricerca di stringhe esatto non è un buon compromesso.

Dovrai sperimentare per trovare l'algoritmo di ricerca fuzzy più accurato e più rapido per il tuo caso d'uso, e dovrai decidere se è più veloce eseguire il calcolo nel DB o su un app server. Si riduce all'architettura della tua app.

modifica: quando hai a che fare con sequel, tratterei tutti i titoli di una serie come aventi lo stesso peso, quindi scegli la risposta più appropriata in base a un fattore esterno. Per la versione iniziale del tuo software, forse basta ordinare per data di uscita del film. Per una seconda versione, esegui il polling di un'API esterna per trovare il titolo più raro. Per una terza versione, forse raccogli alcune metriche utente per trovare il risultato più pertinente (ad esempio, se l'utente preferisce regolarmente sequel sugli originali, dai al sequel un punteggio più alto).

    
risposta data 09.03.2015 - 21:09
fonte

Leggi altre domande sui tag