Algorytm obliczający wagę w mechanizmie autocomplete

Pracuję właśnie nad mechanizmem completion (autocomplete) w wyszukiwarce 4programmers.net. Chodzi o to aby wyszukiwarka potrafiła podpowiedzieć tytuły - np. wątków, po wpisaniu pierwszych liter. (więcej o tym w wątku: Autocomplete w polu wyszukiwarki)

Chciałbym aby wyszukiwarka brała pod uwagę popularność danego wątku (liczbę głosów oddanych na 1 post), liczbę odpowiedzi czy datę ostatniego postu. I tak np. po wpisaniu słowa ile, na górze wyników miałby znaleźć się wątek Ile zarabiacie (bo jest dość popularny). W tym celu trzeba zapisywać do elasticsearch "wagę" danej podstrony po której będą sortowane wyniki. I tutaj następuje moje pytanie, jaki wzór najlepiej by się tutaj sprawdził?

Np.: waga = (1 * ilosc_odpowiedzi) + (2 * ilosc_lapek_w_gore) + (( timestamp_napisania_ostatniego_posta - timestamp_roku_2000) / 600000)?

Oczywiście, im starsze wątki (brak aktywności), tym powinny mieć niższą wagę. Wstawiłem ostatnie 1000 wątków z kategorii Off-topic do Excela. Możesz sobie popatrzeć: https://docs.google.com/spreadsheets/d/1to9CIRXwlHP50BnqAcO6anrwaUEMzQdrGyEoZQi28_s/edit?usp=sharing

Po zastosowaniu tego wzoru i szukaniu po słowie jakie wynik jest następujący:

Może macie jednak lepszy pomysł?

Brałbym jeszcze pod uwagę, czy temat ma zaakceptowaną odpowiedź.

Generalnie do tego się używa trie, tu są wątki:
https://stackoverflow.com/questions/2901831/algorithm-for-autocomplete
https://stackoverflow.com/questions/1783652/what-is-the-best-autocomplete-suggest-algorithm-datastructure-c-c
Można by jeszcze userowi "cachować" zapytania, tak jak nam to robi, np. firefox.
Co do samego wzoru, nie widzę wagi od zaakceptowanej odpowiedzi, koniecznie powinna być, imo, nawet dobrze żeby eliminowała timestamp.
Fajne by też było to: zaczynam pisać st, coś mi tam wychodzi, dodaję sto, to spodziewam się: stos jako lista i inne, ale chciałbym też zobaczyć, np. implementacja stosu. I tu jest właśnie: prefix czy postfix? Ciekawe czy da się to efektywnie (żeby podpowiedź nie wyświetliła się po tym, jak user już wpisze frazę :) ) zmiksować

@lion137: dzięki za linki. Może źle się wyraziłem. Nie potrzebuje zaimplementować algorytmu szukania ponieważ tym zajmuje się elasticsearch. O to nie muszę się martwić.

Potrzebuje jedynie wymyślić wzór/algorytm, który ustawi wagę dla każdej podstrony, na podstawie której wyniki będą posortowane. Słuszna uwaga, aby zaakceptowany wątek miał większą wagę niż ten niezaakceptowany.

Jeżeli chodzi o wyszukiwanie, takie o którym mówisz to da się to zrobić. Mając wątek implementacja stosu należy, zindeksować w mechanizmie autocomplete dwie frazy, przypisane do tego wątku. Pierwsza to implementacja stosu, a druga to stosu (drugi wyraz). Wówczas mechanizm znajdzie też słowo znajdujące się po środku.

@Adam Boduch: Dzięki za sprostowanie. Czyli trzeba się skupić nad wzorem, ale obawiam, że tak czy inaczej, bez testowania na produkcji - czyli normalnie :D się nie obejdzie. A Masz tam "cachowanie" w tym elasticsearch?

Umieszczę tutaj listę parametrów ułożoną przeze mnie w poście w poprzednim temacie (tu post: Autocomplete w polu wyszukiwarki), trochę ją poprawiając, grupując i oczywiście aktualizując. Kolejność nadal nie ma znaczenia. Pomijam pomysłodawców.

• Wskaźnik:
  • odpowiedniości dopasowania tytułu wątku względem wyszukiwanego wzorca — skala: [0,1), interpretacja: więcej = lepiej
  • odpowiedniości dopasowania treści pierwszego posta wątku względem wyszukiwanego wzorca — skala: [0,1), interpretacja: więcej = lepiej
  • czy wątek ma zaakceptowaną odpowiedź — skala: {true,false}, interpretacja: ?
• Liczba:
  • głosów na pierwszy post wątku (w domyśle: na wątek) — skala: [0,inf), interpretacja: więcej = lepiej
  • sumaryczna głosów ze wszystkich postów w wątku — skala: [0,inf), interpretacja: więcej = lepiej (?)
  • średnia komentarzy na 1 post wątku — skala: [0,inf), interpretacja: więcej = lepiej (?)
  • odsłon wątku — skala: [0,inf), interpretacja: więcej = lepiej
  • uczestników w wątku — skala: [1,inf), interpretacja: więcej = lepiej
  • postów w wątku — skala: [1,inf), interpretacja: ?
• Czas:
  • między momentem/datą założenia wątku a momentem/datą ostatniej aktywności w nim — skala: ?, interpretacja: ?
  • między momentem/datą ostatniej aktywności w wątku a momentem/datą rozpoczęcia wyszukiwania — skala: ?, interpretacja: mniej = lepiej — uwagi: prawdopodobnie tego się nie użyje, bo to na pewno trzeba obliczać na bieżąco przy wyszukiwaniu
  • między momentem/datą opublikowania ostatniego posta a momentem/datą (początku?) roku 2000 — skala: ?, interpretacja: więcej = lepiej
• Rozkład:
  • aktywności w wątku w czasie — skala: [0,1), interpretacja: więcej = szczyt bliżej dnia dzisiejszego = ?

@Adam Boduch, wszystkie te parametry mogą zmieniać się dla wątku w czasie, więc każdy musi zostać kiedyś obliczony. Podaj może, które z tych parametrów kiedy są obliczane (na przykład, czy sumaryczna liczba głosów dla wszystkich postów wątku jest obliczana po każdym nowym głosie, czy dopiero przy żądaniu jej, czy może w ogóle nie ma takiej funkcjonalności w systemie).

@Adam Boduch:

jakiego typu cachowanie masz na myśli?

Coś podobnego co robi, np., moje duckduckgo na telefonie, wpisywałem: "spaghetti putanesca kwestia smaku", jak za godzinę zacząłem "spa", to w podpowiedziach miałem już całą tę frazę, linka do kwestii smaku na który wszedłem, linka do wcześniejszego spaghetti bolognese na kwestii smaku na który wchodziłem. Nie na początku, pierwsze były inne, zapewne wybierane przez algorytm jako pierwsze dla "spa".

@lion137: takie coś trzeba samemu sobie oprogramować i mam nawet pomysł jak to zrobić :)

@Silv: w tabeli topics jest zapisana liczba głosów oddanych na 1 post w wątku.

Ktoś coś? Jakiś pomysł? Wydaje mi się że jednak liczba głosów czy odpowiedzi powinna mieć wyższą wagę niż zaproponowane przeze mnie 1 czy 2.

Ja bym do wagi ilości odpowiedzi dodał wagę kto udzielił odpowiedzi (jaki ma score) i jak obszerna była odpowiedź (odpowiedzi na parę wyrazów raczej nie niosą wartości).
Pytanie jak uwzględnić linki? PageRank?

Jest jeszcze problem ciętych ripost, które często zbierają dużo głosów.

Ja bym wziął pod uwagę kategorię, do której należy wątek, np.:

• kategorie o programowaniu są wyżej, niż off-topic,
• propozycje są grupowane według kategorii po aktywności.

MarekR22 napisał(a):

Ja bym do wagi ilości odpowiedzi dodał wagę kto udzielił odpowiedzi (jaki ma score) i jak obszerna była odpowiedź (odpowiedzi na parę wyrazów raczej nie niosą wartości).

a dlaczego nie? lepszy rozwlekły elaborat niż dwa słowa trafiające w istotę problemu? coś w tych narzekaniach na promowanie ekstrawertyków w IT widać jest zgodne z prawdą ;)

Szkoda, że nikt nie zaproponował jakiegoś konkretnego wzoru, bo właściwie o to mi chodziło w tym wątku :)

Póki co doszedłem do takiego wzoru:

waga = (10 * ilosc_odpowiedzi) + (20 * ilosc_lapek_w_gore) + (czy_watek_zaakceptowany ? 100 : 0) + (( timestamp_napisania_ostatniego_posta - timestamp_roku_2000) / 600000)?

Większą wagę ma to czy wątek jest zaakceptowany niż to ile ma odpowiedzi. Trzeba tutaj jednak będzie dodać jakiś limit (max()) bo wątek który ma np. 180 odpowiedzi, ale jest z 2012 roku jest bardzo wysoko punktowany, własnie ze względu na liczbę odpowiedzi.

Liczba wyświetleń + 1000 * liczba głosów + 100 * liczba odpowiedzi - log10(current_timestamp - topic_timestamp)

Potencjalnie dodać jakieś 10k za zaakceptowaną odpowiedź i zwiększyć wagę poprawki czasu. Wynik:

		Odpowiedzi	Głosy	Wyświetleni	Data	Timestamp
324168	W jakie gry gracie?	112	3	12518	2019-03-17 10:51:12+00	1552819872
335618	Na jakie przyjemności, hobby wydajecie pieniądze?	46	1	5898	2020-01-27 18:35:49+00	1580150149
335923	Do jakiego majątku doszliście jako programiści?	45	0	5707	2020-02-04 12:54:36+00	1580820876
308813	Jakie autko byś wybrał?	27	0	5492	2018-05-08 22:15:24+00	1525817724
304685	Jakie masz poglądy? Lewicowe/Prawicowe/Centrum	27	0	5388	2018-02-17 08:50:19+00	1518857419
306103	Jakie zaburzenia osobowosci macie	15	2	3739	2018-03-14 20:21:12+00	1521058872
313637	Jakie macie komputery(laptopy)	24	1	2993	2018-08-18 19:58:41+00	1534622321
304798	Jakiego sprzętu używacie w pracy ?	24	0	3346	2018-02-19 17:19:20+00	1519060760
327491	Jakie plany na wakacje	20	1	2608	2019-06-04 20:19:35+00	1559679575
331167	Jakiej przeglądarki używacie?	30	0	2044	2019-09-26 21:27:04+00	1569533224
331948	Jakie macie sposoby na walkę z brakiem kreatywności/pomysłowości?	24	0	1873	2019-10-22 09:58:35+00	1571738315
327021	Programiści, na jakiej zasadzie programujecie ?	16	0	2447	2019-05-23 15:53:42+00	1558626822
314780	Jakie stawiacie sobie cele w życiu i w karierze zawodowej?	14	0	1890	2018-09-11 14:46:13+00	1536677173
328173	Jakie filmy SF polecacie.	19	0	1188	2019-06-21 12:09:31+00	1561118971
327631	Termodynamika - jakie ustawienie wiatraka szybciej schłodzi pokój? Na zewnątrz czy do środka?	10	1	569	2019-06-07 23:07:10+00	1559948830
325673	Jakie sneakersy możecie polecić(z doświadczenia! ;) ) na lato?	9	0	928	2019-04-20 11:59:29+00	1555761569
336671	Jakie jest wasze ulubione kolorowanie tekstu?	4	1	193	2020-02-23 06:34:54+00	1582439694
336557	Jakie znacie tricki na tabliczkę mnożenia do 100?	9	0	385	2020-02-19 21:36:17+00	1582148177
309493	Darmowe kursy zawodowe w KRK - (prawdziwe meskie zawody, nie jakies tam klepanie na kompie)	0	1	267	2018-05-22 07:26:09+00	1526973969
306753	Jakie ubezpieczenie OC na B2B - działalność gospodarczą	0	0	1107	2018-03-26 09:00:24+00	1522054824
304963	Pobranie stanu konta z jakiegos banku.	4	0	663	2018-02-22 18:14:50+00	1519323290
314416	Nowe technologie, czyli jakie?	3	0	634	2018-09-03 13:21:42+00	1535980902
336110	Platforma Crowdfunding jakie sa koszta utrzymania itd ?	5	0	327	2020-02-08 18:05:21+00	1581185121
335993	Jakie fora oprócz 4p odwiedzacie?	4	0	418	2020-02-05 18:51:43+00	1580928703
305556	Jakie API dla SMS polecacie?	2	0	532	2018-03-05 19:42:02+00	1520278922
324199	Czy jest jakieś API do CEPIK	1	0	381	2019-03-17 21:55:16+00	1552859716
333391	Czy w Warszawie są jakieś fajne biura do wynajęcia ?	1	0	336	2019-11-27 22:37:48+00	1574894268
323838	Jakie przewodniki turystyczne polecacie?	2	0	180	2019-03-09 14:02:43+00	1552140163
328687	Bob Lazar - jakie macie zdanie na jego temat?	0	0	311	2019-07-07 14:38:05+00	1562510285

@Afish: dzięki za konkretną odpowiedź.

Niestety, tak jak pisałem w 1 poście, waga musi być zapisana do elasticsearch, czyli nie mogę jej obliczać w momencie wyszukiwania, a w momencie zapisu danych. Z tego powodu current_timestamp nie jest dostępny.

Podobnie jak liczba wyświetleń. Ta z kolei zmienia się tak często że wymagałoby to reindeksacji w elasticsearch całego wątku za każdym razem gdy ktoś go przeczyta.

Jak często reindeksujesz?

Obecnie jest reindeksowany po napisaniu jakiegokolwiek postu, edycji no i oczywiście - usunięcia :) Dodatkowo teraz trzeba będzie reindeksować po oddaniu głosu na 1 post czy zaakceptowaniu odpowiedzi.

Czemu ten czas taki ważny, na stacku często się znajduje stare odpowiedzi, co w nich złego skoro rozwiązały problem?

lion137 napisał(a):

Czemu ten czas taki ważny, na stacku często się znajduje stare odpowiedzi, co w nich złego skoro rozwiązały problem?

Tutaj mówimy nie stricte o samem mechanizmie wyszukiwania, a jedynie autocomplete. Oczywiście nie ma nic złego w starych wątkach które rozwiązały problem. Dlatego waga wątków zaakceptowanych powinna być dość wysoka :)

A może zamiast na czuja ustawiać wagi nie było by lepiej najpierw arbitralnie posortować pewną ilość wątków o różnej jakości,
a potem sprawdzać w jakim stopni metryka odwzorowuje pożądaną kolejność?

Wtedy głównym problemem (wysiłkiem) jest stworzenie takiej próbki takich wątków i ich kolejności.
Jednak społeczność mogła by pomóc w ocenie jakości wybranych wątków.

Wobec braku innych alternatyw ruszyłem już z tym zadaniem i zaimplementowałem ten mój wzór. ALE nie oznacza to że nie można tego będzie zmienić :)

@MarekR22: Jeżeli jesteś chętny do pomocy w tej kwestii sortowania to jak najbardziej :)