Optymalne przechowywanie wektora trójki wyrazów

Question

hejka

Czy znacie jakąś strukturę danych, która w optymalny sposób przechowywałaby połączenie 3 wyrazów?

przykładowe dane:

1. ala, ma, kota
2. ala, ma, psa
3. ala, ma, żyrafę

 

Dodam tylko, że kolejność ma znaczenie.

Z góry dzięki!

Comments

Czytaj komentarze dokładniej. Pierwsza część nie była do Ciebie, poza tym "proszę Cię podawaj wszystkie informację w pytaniu, a nie, że wszystko trzeba wyciągać". Niżej podałem link, w który warto zajrzeć, z złożoności obliczeniowej wygląda obiecująco.

---

 leci jedno zapytanie where word1=X and word2=X

Czy w praktyce będzie zapytanie zawsze o pierwsze słowo, plus potencjalnie o drugie, plus potencjalnie o trzecie? To znaczy, czy może się zdarzyć że będzie zapytanie z samym `where word2=Y`?

Tymczasowo założę że nie i że zawsze jest "słownikowo". To wtedy widzę takie spostrzeżenia/opcje:
- tak naprawdę nie trzeba tego traktować jak trzy słowa. "where word1=X and word2=Y" jest równoważne "where sentence.startswith("X Y")"; można by więc się zastanowić na pojedynczą kolumną i zwykłym indeksie MySQLowym (który ogarnie startswith).

- alternatywnie: można na poziomie kodu (lub bazy) trzymać słownik słowników słow. To znaczy {ala: {ma: [kota, psa, żyrafę}}. To jest spora deduplikacja danych; na przykład taki 500MB (20mil wierszy) plik załadowałem do Pythona i całość zajmuje 180MB. Tak się składa że to też hash table o którym wspomniał tkz; masz zapytania typu "where word1=X and word2=Y" praktycznie natychmiastowo.

- powyższe można też zrealizować w zwykłych tabelach SQLowych, przez zrobienie kilku tabel zamiast jednej na wszystkie trzy kolumny; masz wtedy podobną deduplikację.

- wcześniej pytałeś o gotowe rozwiązania; kojarzę na przykład ClickHouse, Apache ORC czy inne kolumnowe bazy... ale ogólnie wydaje mi się że przy takiej skali jeszcze bym próbował się trzymać zwykłych baz.

---

Czy w praktyce będzie zapytanie zawsze o pierwsze słowo, plus potencjalnie o drugie, plus potencjalnie o trzecie? To znaczy, czy może się zdarzyć że będzie zapytanie z samym `where word2=Y`?

zapytania typu: word1=X && word2=Y oraz word2=X && word3=Y

 

alternatywnie: można na poziomie kodu (lub bazy) trzymać słownik słowników słow. To znaczy {ala: {ma: [kota, psa, żyrafę}}.

wszystko fajnie, wtedy zwykle drzewo zalatwia sprawe, problem w tym ze czasami trzeba przeszukac od prawej do lewej czyli word2=X and word3=X

 

---

No to... jak by tych danych nie przechowywać, to gdzieś jakaś postać indeksu musi być, może dwa, może trzy. To wciąż nie jest taka skala, że miejsce na dysku oraz zużycie pamięci mogłyby być wielkimi problemami IMO.

---

trudno, jak coś znajdę to napiszę