Somiglianza tra stringhe di linea

Question

Ho un numero di tracce registrate da un GPS, che più formalmente possono essere descritte come un numero di stringhe di linea.

Ora, alcune delle tracce registrate potrebbero essere registrazioni dello stesso percorso, ma a causa di imprecisioni nel sistema GPS, il fatto che le registrazioni siano state effettuate in occasioni separate e che potrebbero essere state registrate viaggiando a velocità diverse, non verranno corrispondono perfettamente, ma sembrano comunque abbastanza vicini quando visualizzati su una mappa da un essere umano per determinare che si tratta effettivamente dello stesso percorso che è stato registrato.

Voglio trovare un algoritmo che calcoli la somiglianza tra due stringhe di linee.Ho escogitato alcuni metodi fatti in casa per farlo, ma vorrei sapere se questo è un problema che dispone già di buoni algoritmi per risolverlo.

Come calcoleresti la somiglianza, dato che mezzi simili rappresentano lo stesso percorso su una mappa?

Modificare: Per chi non è sicuro di cosa sto parlando, guarda questo link per una definizione di cosa sia una stringa di linea: http://msdn.microsoft.com/en-us/library/bb895372.aspx - Io sono non chiedendo informazioni sulle stringhe di caratteri.

Answer 1

Calcola il Distanza Fréchet su ciascuna coppia di tracce.La distanza può essere utilizzata per valutare la somiglianza delle tue tracce.

Avviso matematica: Fréchet è stato un pioniere nel campo della spazio metrico che è rilevante per il tuo problema.

Answer 2

Aggiungerei un buffer attorno alla prima riga in base al probabile errore stimato e quindi determinerei se la seconda riga rientra interamente nel buffer.

Answer 3

Per determinare lo "stesso percorso", creare l'insieme minimo di vettori di percorso normalizzati, calcolare le differenze di potenza totali e confrontare il totale con una misura di qualità.

1. Normalizza i waypoint GPS sulla lunghezza totale del percorso,
2. percorri insieme i vettori dei percorsi, creando una nuova serie di vettori di percorso per ciascun percorso in base al vettore più breve in ciascun punto di passaggio,
3. calcolare le differenze di potenza totale tra i punti finali di ciascun vettore nei percorsi normalizzati ponderati per la lunghezza del vettore e
4. confrontare con una misura di qualità.

Ottimizza visivamente la potenza delle differenze (inizia con, ad esempio, differenze al quadrato) e la misura della qualità (ad esempio come percentuale delle differenze di potenza totali).Questo algoritmo produce una misura continua della qualità della corrispondenza del percorso nonché un risultato binario (i percorsi sono gli stessi?)

Paul Tomblin ha detto:Vorrei aggiungere un buffer attorno alla prima riga in base all'errore probabile stimato, quindi determinare se la seconda riga si adatta interamente all'interno del buffer.

È possibile modificare l'algoritmo mentre vengono confrontati gli endpoint del vettore normalizzato.Potresti determinare se qualsiasi differenza di endpoint fosse superiore a una certa dimensione (implementando l'idea del buffer di Paul) o forse, se gli endpoint fossero al di fuori del "buffer", utilizzare questo fatto per ignorare la differenza di endpoint, consentendo un confronto ignorando i viaggi secondari.

Answer 4

Potresti camminare lungo ogni punto (Pa) di LineString A e misurare la distanza da Pa al segmento di linea più vicino di LineString B, calcolando la media di ciascuna di queste distanze.

Questo non è un metodo rapido o perfetto, ma dovrebbe essere in grado di fornire un numero utile ed è piuttosto veloce da implementare.

Le linee iniziano e finiscono in punti simili o hanno estensioni molto diverse?

Answer 5

Se consideri una singola stringa di linea come una sequenza di punti [x,y] (o punti [x,y,z]), allora potresti calcolare la somiglianza tra ciascuna coppia di stringhe di linea utilizzando la formula Needleman-Wunsch algoritmo.Come descritto nell'articolo di Wikipedia di riferimento, l'algoritmo Needleman-Wunsch richiede una "matrice di similarità" che definisce la distanza tra una coppia di punti.Tuttavia, sarebbe facile utilizzare una funzione anziché una matrice.Nel tuo caso potresti semplicemente usare il 2D Distanza euclidea (o una funzione euclidea 3D se i tuoi punti hanno elevazione) per fornire la distanza tra ciascuna coppia di punti.

Answer 6

In realtà mi schiero con la persona (Aaron F) che ha detto che potresti essere interessato al problema della distanza di Levenshtein (e ha citato Questo).La sua risposta mi sembra finora la migliore.

Più nello specifico, la distanza di Levenshtein (detta anche distanza di modifica), non misura rigorosamente la distanza carattere per carattere, ma consente anche di effettuare inserimenti ed eliminazioni.Il miglior algoritmo per questa misura della distanza può essere calcolato in tempo quadratico (piuttosto lento se le stringhe sono lunghe), ma i biologi computazionali hanno un'euristica abbastanza buona per questo, che potrebbe interessarti da solo.Guardare RAFFICA E VELOCE.

Nel tuo problema, sembra che tu abbia a che fare con le differenze tra stringhe di numeri e che ti preoccupi dei numeri.Se fornisci maggiori informazioni, potrei essere in grado di indirizzarti alla variante giusta di BLAST/FASTA/etc per i tuoi scopi.In ogni caso, potresti considerare di adattare BLAST e FASTA alle tue esigenze.Sono abbastanza semplici.

1: http://en.wikipedia.org/wiki/Levenshtein_distance, http://www.nist.gov/dads/HTML/Levenshtein.html