Risoluzione di categorie ambigue in un elenco ordinato

Question

Facciamo un esempio concreto e speriamo di poter essere chiaro. Supponiamo che l'elenco (ordinato) dei mesi:

  

Gennaio < Febbraio & Lt; Marzo & Lt; ... <   Dicembre

(con numeri interi che rappresentano i mesi, a base zero), tale che

  

Jan è 0, Feb è 1, ..., Dec è 11.

Ora supponiamo che non abbia accesso al nome completo dei mesi e che mi venga dato il seguente elenco, in cui i mesi sono stati abbreviati nella loro prima lettera e e sta per una categoria vuota, come in questo modo:

  

e, F, e, e, e

Se creo un elenco di " mesi non ambigui " (f: 1, s: 8, o: 9, n: 10, d: 11), posso riempire le categorie vuote calcolando prima la prima categoria (usando sottrazione e mod 12), quindi scrivendo il resto da lì . Tuttavia, supponiamo che mi venga fornito l'elenco

  

e, A, e, e, J, e

Quindi posso (intuitivamente) calcolare che sebbene A sia ambiguo (potrebbe essere aprile o agosto), in questo contesto può essere solo aprile, dal momento che agosto non ha J s che lo segue dopo 2 categorie. Una volta trovato questo, posso nuovamente calcolare tutto dall'inizio.

La mia domanda, infine, è: esiste una soluzione analitica (funzione, algoritmo) per questo problema o è la mia unica speranza di usare la forza bruta per definire ogni potenziale relazione? Per alcuni esempi, nessun algoritmo / funzione di disambiguazione può funzionare: considera il caso in cui ho un J seguito da 11 e , seguito da un J seguito da 11 e ... Dal momento che c'è un anno in mezzo, non riesco a chiarire J in gennaio, giugno o luglio.

Risposta : ho finito per scrivere la risposta di Il-Bhima, perché in questo caso in particolare i regex sono ok, anche con un tempo di esecuzione più alto O (mn). Tuttavia, ho accettato la risposta di Ben come la risposta corretta perché riassume le altre (menziona la soluzione regex), ma suggerisce anche un modo migliore usando l'algoritmo KMP O (m + n), anche se questo è per un numero maggiore di stringhe contro per abbinare il modello. Grazie a tutti.

Answer 1

Non sono sicuro se questo è esattamente quello che stai cercando, ma potresti usare un algoritmo di ricerca delle stringhe KMP per risolvere questo problema.

La modifica dovrebbe corrispondere a qualsiasi cosa rispetto alla categoria vuota. Potrebbe persino trovare tutti i possibili valori per te, come la J con 11 e come hai menzionato.

Puoi anche utilizzare una macchina a stati finiti per determinare le possibilità, questo è ciò che < a href = "http://en.wikipedia.org/wiki/Regular_expression" rel = "nofollow noreferrer"> espressione regolare farebbe.

Answer 2

Il modo più semplice per farlo è usare espressioni regolari. Supponiamo di voler abbinare e, A, e, e, J, e.

Costruisci la seguente espressione regolare: r = ".A..J."

Sia c la nostra stringa di controllo:

  c = "JFMAMJJASONDJFMAMJJASOND"

Ora cerchiamo tutte le corrispondenze di r nella stringa "JFMAMJJASOND" in cui l'indice iniziale di una corrispondenza si trova nella prima metà di O(nm).

In generale, questo potrebbe non essere il metodo più efficiente. La soluzione più ingenua, che tenta di abbinare il modello a ogni spostamento ciclico della stringa di controllo n viene eseguito in m tempo, dove JFMAMJJASOND è la lunghezza del modello, <=> è la lunghezza della stringa di controllo ( nel nostro caso <=>).

Answer 3

Possiamo basarci un po 'sulla risposta di Il-Bhima per il caso generale. Innanzitutto, riconosciamo che le uniche coppie veramente ambigue di A, M o J sono due J distanti tra loro sei mesi o due della stessa lettera distanti un anno. Qualsiasi altra combinazione produrrà una corrispondenza non ambigua nella stringa di controllo. (Ho creato una tabella di tutte le possibili combinazioni per dimostrarlo.)

Quindi tutto ciò di cui hai bisogno dall'intero elenco iniziale sono due mesi la cui distanza mod 12 non è 0 o 6. Puoi quindi creare una piccola espressione regolare da abbinare alla stringa di controllo. In alternativa, è possibile creare una tabella di ricerca contenente la coppia ordinata e le distanze tra i mesi.