Rompere una stringa a parte in una sequenza di parole

Question

Recentemente ho incontrato alla seguente domanda dell'intervista:

Dato uno stringa di input e un dizionario di parole, implementare un metodo che rompe la stringa di input in uno spazio- stringa separata di parole del dizionario che un motore di ricerca potrebbe utilizzare per "Intendevi?" Ad esempio, un input di "applepie" dovrebbe produrre un output di "torta di mele".

Non riesco a ottenere una soluzione ottimale per quanto riguarda la complessità. Qualcuno ha qualche suggerimento su come farlo in modo efficiente?

Answer 1

Sembra che la domanda sia esattamente il problema del mio colloquio, fino all'esempio che ho utilizzato nello post in The Noisy Channel. Sono contento che ti sia piaciuta la soluzione. Sono abbastanza sicuro che non puoi battere la soluzione di programmazione/memoizzazione dinamica O (n^2) che descrivo per le prestazioni nel caso peggiore.

Si può fare meglio nella pratica se il dizionario e l'input non sono patologici. Ad esempio, se è possibile identificare in tempo lineare le sottostringhe della stringa di input sono nel dizionario (ad es., con un trie) e se il numero di tali sottostringhe è costante, allora il tempo complessivo sarà lineare. Naturalmente, questo è un sacco di presupposti, ma i dati reali sono spesso molto più belli di un caso peggiore patologico.

Ci sono anche divertenti varianti del problema per rendere più difficile, ad esempio l'enumerazione tutte le segmentazioni valide, l'output di una migliore segmentazione basata su qualche definizione delle migliori, la gestione di un dizionario troppo grande per entrare in memoria, e la manipolazione segmentazioni inesatte (ad esempio, correggere errori di ortografia). Sentiti libero di commentare il mio blog o altrimenti contattami per dare seguito.

Answer 2

Un'opzione sarebbe quella di memorizzare tutte le parole inglesi valide in un trie. Una volta che hai fatto questo, potresti iniziare a camminare il trie dalla radice verso il basso, seguendo le lettere nella stringa. Ogni volta che si trova un nodo che è contrassegnato come una parola, avete due opzioni:

1. rompere l'ingresso a questo punto, o
2. Continua l'estensione della parola.

È possibile affermare di aver trovato una corrispondenza una volta interrotto l'input in un insieme di parole che sono tutte legali e che non sono rimasti caratteri rimanenti. Dato che ad ogni lettera hai un'opzione forzata (o stai costruendo una parola che non è valida e dovrebbe fermarsi -oppure puoi continuare ad estendere la parola) o due opzioni (divisa o continua), potresti implementare questa funzione utilizzando la ricorsione esaustivo:

PartitionWords(lettersLeft, wordSoFar, wordBreaks, trieNode): 
    // If you walked off the trie, this path fails. 
    if trieNode is null, return. 

    // If this trie node is a word, consider what happens if you split 
    // the word here. 
    if trieNode.isWord: 
     // If there is no input left, you're done and have a partition. 
     if lettersLeft is empty, output wordBreaks + wordSoFar and return 

     // Otherwise, try splitting here. 
     PartitinWords(lettersLeft, "", wordBreaks + wordSoFar, trie root) 

    // Otherwise, consume the next letter and continue: 
    PartitionWords(lettersLeft.substring(1), wordSoFar + lettersLeft[0], 
        wordBreaks, trieNode.child[lettersLeft[0]) 

Nel caso peggiore patologicamente questo elenco di tutte le partizioni della stringa, che può t esponenzialmente lungo. Tuttavia, ciò si verifica solo se è possibile suddividere la stringa in un numero enorme di modi in cui tutti iniziano con parole inglesi valide ed è improbabile che si verifichino nella pratica. Se la stringa ha molte partizioni, potremmo passare molto tempo a trovarle, però. Ad esempio, considera la stringa "dotheredo". Possiamo dividere questo molti modi:

do the redo 
do the red o 
doth ere do 
dot here do 
dot he red o 
dot he redo 

Per evitare questo, si potrebbe desiderare di istituire un limite del numero di risposte si segnala, forse due o tre.

Poiché interrompiamo la ricorsione quando usciamo dal trie, se mai proviamo uno split che non lascia il resto della stringa valido, lo rileveremo abbastanza rapidamente.

Spero che questo aiuti!

Answer 3

Questo link descrive questo problema come una domanda di intervista perfetta e fornisce diversi metodi per risolverlo. In sostanza si tratta di recursive backtracking. A questo livello produrrebbe una complessità O (2^n). Una soluzione efficiente che utilizza la memoizzazione potrebbe portare questo problema a O (n^2).

Answer 4

importazione java.util. *;

class Position { 
    int indexTest,no; 
    Position(int indexTest,int no) 
    { 
     this.indexTest=indexTest; 
     this.no=no; 
    } } class RandomWordCombo { 
    static boolean isCombo(String[] dict,String test) 
    { 
     HashMap<String,ArrayList<String>> dic=new HashMap<String,ArrayList<String>>(); 
     Stack<Position> pos=new Stack<Position>(); 
     for(String each:dict) 
     { 
      if(dic.containsKey(""+each.charAt(0))) 
      { 
       //System.out.println("=========it is here"); 
       ArrayList<String> temp=dic.get(""+each.charAt(0)); 
       temp.add(each); 
       dic.put(""+each.charAt(0),temp); 
      } 
      else 
      { 
       ArrayList<String> temp=new ArrayList<String>(); 
       temp.add(each); 
       dic.put(""+each.charAt(0),temp); 
      } 
     } 
     Iterator it = dic.entrySet().iterator(); 
    while (it.hasNext()) { 
     Map.Entry pair = (Map.Entry)it.next(); 
     System.out.println("key: "+pair.getKey()); 
     for(String str:(ArrayList<String>)pair.getValue()) 
     { 
      System.out.print(str); 
     } 
    } 
     pos.push(new Position(0,0)); 
     while(!pos.isEmpty()) 
     { 
      Position position=pos.pop(); 
      System.out.println("position index: "+position.indexTest+" no: "+position.no); 
      if(dic.containsKey(""+test.charAt(position.indexTest))) 
      { 
       ArrayList<String> strings=dic.get(""+test.charAt(position.indexTest)); 
       if(strings.size()>1&&position.no<strings.size()-1) 
        pos.push(new Position(position.indexTest,position.no+1)); 
       String str=strings.get(position.no); 
       if(position.indexTest+str.length()==test.length()) 
        return true; 
       pos.push(new Position(position.indexTest+str.length(),0)); 
      } 
     } 
     return false; 
    } 
    public static void main(String[] st) 
    { 
     String[] dic={"world","hello","super","hell"}; 
     System.out.println("is 'hellworld' a combo: "+isCombo(dic,"superman")); 
    } } 

ho fatto simile problema. Questa soluzione fornisce true o false se la stringa data è una combinazione di parole del dizionario. Può essere facilmente convertito per ottenere una stringa separata dallo spazio. La sua complessità media è O (n), dove n: no delle parole del dizionario in una stringa data.

Answer 5

Utilizzando python, possiamo scrivere due funzioni, la prima segment restituisce la prima segmentazione di un pezzo di testo contiguo in parole date un dizionario o None se tale segmentazione non viene trovata. Un'altra funzione segment_all restituisce un elenco di tutte le segmentazioni rilevate. La complessità del caso peggiore è O (n ** 2) dove n è la lunghezza della stringa di input in caratteri.

La soluzione presentata qui può essere estesa per includere correzioni ortografiche e analisi bigram per determinare la segmentazione più probabile.

def memo(func): 
    ''' 
    Applies simple memoization to a function 
    ''' 
    cache = {} 
    def closure(*args): 
     if args in cache: 
      v = cache[args] 
     else: 
      v = func(*args) 
      cache[args] = v 
     return v 
    return closure 


def segment(text, words): 
    ''' 
    Return the first match that is the segmentation of 'text' into words 
    ''' 
    @memo 
    def _segment(text): 
     if text in words: return text 
     for i in xrange(1, len(text)): 
      prefix, suffix = text[:i], text[i:] 
      segmented_suffix = _segment(suffix) 
      if prefix in words and segmented_suffix: 
       return '%s %s' % (prefix, segmented_suffix) 
     return None 
    return _segment(text) 


def segment_all(text, words): 
    ''' 
    Return a full list of matches that are the segmentation of 'text' into words 
    ''' 
    @memo 
    def _segment(text): 
     matches = [] 
     if text in words: 
      matches.append(text) 
     for i in xrange(1, len(text)): 
      prefix, suffix = text[:i], text[i:] 
      segmented_suffix_matches = _segment(suffix) 
      if prefix in words and len(segmented_suffix_matches): 
       for match in segmented_suffix_matches: 
        matches.append('%s %s' % (prefix, match)) 
     return matches 
    return _segment(text) 


if __name__ == "__main__":  
    string = 'cargocultscience' 
    words = set('car cargo go cult science'.split()) 
    print segment(string, words) 
    # >>> car go cult science 
    print segment_all(string, words) 
    # >>> ['car go cult science', 'cargo cult science']