Jestem pewien, że jest na to post, ale nie mogłem znaleźć takiego pytania. Rozważ następujące:

Mamy słownik słów dostępnyDostajemy wiele akapitów słów i chciałbym móc przewidzieć następne słowo w zdaniu podanym na tym wejściu.

Powiedzmy, że mamy kilka zdań takich jak „Cześć, nazywam się Tom”, „Jego imię to jerry”, „Idzie tam, gdzie nie ma wody”. Sprawdzamy tabelę mieszania, jeśli istnieje słowo. Jeśli tak nie jest, przypisujemy mu unikalny identyfikator i umieszczamy go w tabeli mieszania. W ten sposób zamiast przechowywać „łańcuch” słów jako kilka ciągów, możemy po prostu mieć listę unikalnych identyfikatorów.

Powyżej mielibyśmy na przykład (0, 1, 2, 3, 4), (5, 2, 3, 6) i (7, 8, 9, 10, 3, 11, 12). Pamiętaj, że 3 to „jest” i dodaliśmy nowe unikalne identyfikatory, gdy odkryliśmy nowe słowa. Więc powiedzmy, że otrzymaliśmy zdanie „jej imię jest”, byłoby to (13, 2, 3). Chcemy wiedzieć, biorąc pod uwagę ten kontekst, jakie powinno być następne słowo. To jest algorytm, o którym myślałem, ale nie uważam go za wydajny:

Mamy listę łańcuchów N (obserwowane zdania), w których łańcuch może być ex. 3,6,2,7,8.Każdy łańcuch ma średnią wielkość M, gdzie M jest średnią długością zdaniaOtrzymujemy nowy łańcuch o rozmiarze S, np. 13, 2, 3 i chcemy wiedzieć, jakie jest najbardziej prawdopodobne następne słowo?

Algorytm:

Najpierw zeskanuj całą listę łańcuchów dla tych, którzy zawierają pełne dane wejściowe S (13,2,3, w tym przykładzie). Ponieważ musimy skanować łańcuchy N, każdy o długości M i porównywać litery S naraz, jego O (N * M * S).

Jeśli w naszym skanie nie ma łańcuchów, które mają pełne S, następne skanowanie przez usunięcie najmniej znaczącego słowa (tj. Pierwszego, więc usuń 13). Teraz skanuj w poszukiwaniu (2,3) jak w 1 w najgorszym przypadku O (N * M * S), który jest naprawdę S-1.

Kontynuuj skanowanie w ten sposób, aż otrzymamy wyniki> 0 (jeśli w ogóle).

Tally kolejne słowa we wszystkich pozostałych łańcuchach, które zebraliśmy. Możemy użyć tabeli mieszania, która liczy się za każdym razem, gdy dodajemy, i śledzi najbardziej dodane słowo. O (N) najgorszy przypadek, O (1), aby znaleźć maksymalne słowo.

Maksymalnie znalezione słowo jest najbardziej prawdopodobne, więc zwróć je.

Każde skanowanie zajmuje najgorszy przypadek O (M * N * S). Dzieje się tak, ponieważ istnieją N łańcuchów, każdy łańcuch ma M liczb i musimy sprawdzić numery S, aby nałożyć mecz. Skanujemy S razy najgorszy przypadek (13,2,3, a następnie 2,3, a następnie 3 dla 3 skanów = S). Zatem całkowita złożoność wynosi O (S ^ 2 * M * N).

Więc jeśli mamy 100 000 łańcuchów i średnią długość zdania 10 słów, szukamy 1 000 000 * S ^ 2, aby uzyskać optymalne słowo. Oczywiście, N >> M, ponieważ długość zdania nie jest skalowana z liczbą obserwowanych zdań w ogóle, więc M może być stałą. Następnie możemy zmniejszyć złożoność do O (S ^ 2 * N). O (S ^ 2 * M * N) może być jednak bardziej pomocny w analizie, ponieważ M może być znaczną „stałą”.

Może to być kompletne błędne podejście do tego typu problemów, ale chciałem podzielić się swoimi przemyśleniami, zamiast tylko rażąco prosić o pomoc. Powodem skanowania jest to, że chcę skanować tylko tyle, ile muszę. Jeśli nic nie ma pełnego S, po prostu przycinaj S, aż niektóre łańcuchy się dopasują. Jeśli nigdy się nie zgadzają, nie mamy pojęcia, co przewidzieć jako następne słowo! Wszelkie sugestie dotyczące mniej złożonego rozwiązania czasu / przestrzeni? Dzięki!