Łamanie ciąg siebie na sekwencję słów

Question

Niedawno natrafiłem na poniższym wywiadzie pytanie:

Given ciąg wejściowy i słownika wyrazów, wdrożyć metodę, która zrywa ciąg wejściowy w czasoprzestrzeni oddzielony ciąg słów słownikowych, których może użyć wyszukiwarka dla "Czy chodziło Ci o?" Na przykład wejście "applepie" powinno dać wynik "szarlotki".

Nie mogę uzyskać optymalnego rozwiązania w zakresie złożoności. Czy ktoś ma jakieś sugestie, jak to zrobić skutecznie?

Answer 1

Wygląda na to, że jest to dokładnie mój problem z rozmową kwalifikacyjną, aż do przykładu, który użyłem w post w The Noisy Channel. Cieszę się, że podoba Ci się rozwiązanie. Jestem pewien, że nie można pokonać rozwiązania dynamicznego programowania/zapamiętywania O (n^2), które opisuję dla najgorszego przypadku.

W praktyce można zrobić lepiej, jeśli słownik i dane wejściowe nie są patologiczne. Na przykład, jeśli możesz zidentyfikować w czasie liniowym, podciągi łańcucha wejściowego znajdują się w słowniku (np., z trie) i jeśli liczba takich podciągów jest stała, to ogólny czas będzie liniowy. Oczywiście, to wiele założeń, ale prawdziwe dane są często o wiele ładniejsze niż patologiczny najgorszy przypadek.

Istnieją również zabawne warianty problemu, które utrudniają, takie jak wyliczenie wszystkich prawidłowych segmentacji, wygenerowanie najlepszej segmentacji opartej na pewnej definicji najlepszego, obsługa słownika zbyt dużego, aby zmieścić się w pamięci i obsługa niedokładnych segmentacji (np. poprawianie błędów w pisowni). Zapraszam do komentowania na moim blogu lub w inny sposób skontaktuj się ze mną, aby kontynuować.

Answer 2

Jedną opcją byłoby przechowywanie wszystkich poprawnych angielskich słów w trie. Gdy już to zrobisz, możesz zacząć przechodzić triest od korzenia w dół, podążając za literami w łańcuchu. Gdy znajdziesz węzeł, który jest oznaczony jako słowo, masz dwie opcje:

1. złamać wejście w tym momencie, czy
2. dalej rozszerzając słowo.

Możesz stwierdzić, że udało Ci się znaleźć dopasowanie po tym, jak wprowadziłeś dane do zestawu słów, które są legalne i nie zostały pozostałe. Ponieważ przy każdej literze masz jedną wymuszoną opcję (albo budujesz słowo, które nie jest poprawne i powinno zostać przerwane - lub - możesz kontynuować rozszerzanie słowa) lub dwie opcje (podzielone lub kontynuuj), możesz zaimplementować tę funkcję za pomocą wyczerpującego rekurencji:

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]) 

W patologicznie najgorszym przypadku będzie to lista wszystkich partycji napisu, który może t wykładniczo długo. Dzieje się tak jednak tylko wtedy, gdy możesz podzielić łańcuch na wiele różnych sposobów, zaczynając od prawidłowych angielskich słów i jest mało prawdopodobne, aby wystąpił w praktyce. Jeśli łańcuch ma wiele partycji, możemy spędzić dużo czasu na ich znajdowaniu. Rozważmy na przykład ciąg "dotheredo". Możemy podzielić to na wiele sposobów:

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

Aby tego uniknąć, warto wnieść ograniczenie liczby odpowiedzi, Raport, może dwa lub trzy.

Ponieważ odcięliśmy rekursję, gdy wychodzimy z trie, jeśli kiedykolwiek spróbujemy podziału, który nie pozostawi pozostałej części łańcucha, to wykryjemy to dość szybko.

Mam nadzieję, że to pomoże!

Answer 3

Ten link opisuje ten problem jako idealne pytanie do wywiadu i zapewnia kilka metod jego rozwiązania. Zasadniczo dotyczy to recursive backtracking. Na tym poziomie spowodowałoby to złożoność O (2^n). Wydajne rozwiązanie z wykorzystaniem funkcji zapamiętywania może zmniejszyć ten problem do O (n^2).

Answer 4

import 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")); 
    } } 

Zrobiłem podobny problem. To rozwiązanie daje wartość true lub false, jeśli podany ciąg jest kombinacją słów słownikowych. Można go łatwo przekonwertować, aby uzyskać ciąg znaków oddzielony spacją. Jego średnia złożoność to O (n), gdzie n: brak słów słownika w danym ciągu.

Answer 5

Używając Pythona, możemy napisać dwie funkcje, pierwsza segment zwraca pierwszą segmentację fragmentu sąsiedniego tekstu na słowa ze słownikiem lub None, jeśli taka segmentacja nie zostanie znaleziona. Inna funkcja segment_all zwraca listę wszystkich znalezionych segmentacji. Najmniejsza złożoność to O (n ** 2), gdzie n to długość łańcucha wejściowego w znakach.

Przedstawione tutaj rozwiązanie może zostać rozszerzone o poprawki ortograficzne i analizę bigramu w celu określenia najbardziej prawdopodobnej segmentacji.

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']