Algoritmo per confrontare centinaia di documenti simili, ma non identici

6

Ho visto domande simili sul confronto del testo, ma nessuna su una scala così grande.

Ho un cliente con due serie di registrazioni di discorsi, 250 e 550 registrazioni ciascuna. Ciascuna delle registrazioni in ciascun set è unica, ma circa 200 su 250 sono duplicate nel set di 550, e devono eliminare i doppi. Le registrazioni sono state registrate su dispositivi separati, quindi non puoi semplicemente confrontare la lunghezza e il contenuto del file.

Sono disposti a pagare per trascrivere i primi 15 secondi di ogni registrazione, e poi vogliono che io crei un sistema per usare quei trascritti per identificare i duplicati.

Prima di tutto, suppongo che dovrei rimuovere prima la punteggiatura e la maiuscola, perché sono cose che potrebbero cambiare arbitrariamente in base al trascrittore che capita di fare quel file.

La mia prima idea era quella di calcolare semplicemente la distanza di Levenshtein per ogni combinazione di registrazioni, ma non posso immaginare che farlo su una scala così grande (250 x 550) sarebbe efficiente. Poi ho pensato che invece di fare una distanza di Levenshtein, ma usando words come unità invece di caratteri. Ma questo comporterebbe comunque l'esecuzione di un algoritmo 250X550 volte, anche se un algoritmo molto più veloce ogni volta.

Poi pensavo che forse avrei dovuto esaminare ogni documento e creare un dizionario ordinato alfabeticamente con un conteggio del numero di volte in cui ogni parola appare in ogni documento. Quindi potrei semplicemente passare attraverso il dizionario associato a ciascun documento e sottrarre il numero di aspetti di ciascuna parola gli uni dagli altri, per produrre un numero totale di parole non corrispondenti. Questo perde prendendo in considerazione l'ordine delle parole, ma dovrebbe essere molto più veloce.

Quale di questi metodi, o forse un metodo completamente diverso, dovrei usare?

    
posta clum 03.06.2015 - 22:33
fonte

2 risposte

10

Per i report one-shot come questo, l'accuratezza dei risultati e la facilità di verifica dell'algoritmo sono molto, modo più importanti dell'efficienza. Il tuo algoritmo di forza bruta è solo 137.500 combinazioni, confrontando forse una dozzina di parole ciascuna. È un runtime dell'ordine di alcuni secondi, assumendo che tu abbia letto prima tutte le trascrizioni in memoria. Questo è niente rispetto alle ore trascorse facendo la trascrizione e il tuo tempo. Anche se ci volesse un'ora per essere eseguito, sarebbe meglio di un algoritmo veloce che non si sarebbe sicuri avrebbe funzionato. Non renderlo più difficile con te stesso.

    
risposta data 03.06.2015 - 23:02
fonte
1

Il tempo di esecuzione per i calcoli della distanza di modifica è banale, ma sarei preoccupato che i risultati saranno scarsi. Il carattere per carattere sarà rumoroso; Sarei stupito se tu avessi delle corrispondenze esatte. La parola per parola sarà soggetta ai capricci dell'erronea percezione di un plurale, di omofoni, ecc. Ecc.

Detto questo, non c'è niente di sbagliato nel provare prima la cosa più semplice possibile. Se i risultati non sono abbastanza buoni, anche se dopo ci proverei:

  1. Separare la stringa, eseguire un semplice algoritmo di derivazione sulle parole e quindi eseguire i calcoli della distanza di modifica. link per esempio.
  2. Se ciò non produce risultati sufficientemente puliti, tornerei al modello di documento spaziale vettoriale che tu potrebbe facilmente implementare per i tuoi scopi, in 20-30 righe di molti linguaggi di alto livello. (O estrai i pesanti fucili e spingili in Lucene.)
risposta data 04.06.2015 - 01:02
fonte

Leggi altre domande sui tag