Porównywanie odległości levenshtein'a na dużej liczbie słów

0

Hej,

napisałem prośbę na githubie PHP dotyczącą stworzenia funkcji PHP mb_levenshtein która działałaby jak obecna funkcja levenshtein, ale ze wsparciem multibyte, czyli np. zastąpienie 'a' przez 'ą' nie produkowałoby rezultatu 2 tylko 1.

Proszę o wsparcie i dopisanie się tam, że też tego chcecie. Może znajdzie się tu ktoś, komu też by się to przydało, bo implementacje w czystym PHP są kilkadziesiąt razy wolniejsze niż funkcja napisana w C i skompilowana do PHP.

Chcę tego używać do rozpoznawania błędów w tekście i proponowania korekcji, ale trzeba nieznane słowa porównać z prawie 4 milionami słów w j. polskim.

Funkcja levenshtein napisana w C, dla kilku słów robi to w około 10 sek. na średnio mocnej maszynie, ale jest problem z multibyte: używanie funkcji w czystym PHP ze wsparciem multibyte to już jest czas kilka minut - totalnie nieakceptowalny.

Prośba jest tutaj:

https://github.com/php/php-src/issues/10180

Edit: w sumie można korygować punktację za bliskie słowa które wyszły w czystym levenshtein funkcją w PHP (i wtedy z 2 robi się 1) i jest lepiej, ale i tak jest problem kiedy są np. dwa znaki diakrytyczne bo wtedy podstawowa funkcja zwraca zbyt dużą wartość która wychodzi podnad próg tego co podobne - ja przyjmuje że sensowne podobieństwo jest jeżeli levenshtein zwraca ilość pkt = 20% długości słowa do korekcji lub mniej (1 dla słowa o długości mniejszej niż 8).

0

Co takiego robisz, że jest Ci to niezbędne?
Nie wiem na jakich językach pracujesz ale wydaje mi się, że w większości europejskich znaki regionalne można zamienić na odpowiedniki jednobajtowe i nadal efekt porównywania tekstów będzie wystarczająco miarodajny. Do czego potrzebna Ci taka precyzja?

Z drugiej strony jak bardzo tego potrzebujesz to można do PHP dołączyć własną skompilowaną funkcję czy to za pomocą rozszerzeń a jeszcze łatwiej napisać w dowolnym kompilowanym języku prosty serwer/API po TCP/IP czy UDP i korzystać z poziomu PHP.
Natomiast jeśli faktycznie obrabiasz jakieś "mega ilości" danych i czas wykonywania ma kluczowe znaczenie to po prostu nie rób tego w PHP.

3

https://github.com/allegro/allegro-api/issues/6492
Większego gbura dawno nie widziałem xd

0

Nie widzę obecnie możliwości głosowania.

ale trzeba nieznane słowa porównać z prawie 4 milionami słów w j. polskim.

Każde nieznane słowo porównujesz z całym słownikiem?

0
jurek1980 napisał(a):

ale trzeba nieznane słowa porównać z prawie 4 milionami słów w j. polskim.

Każde nieznane słowo porównujesz z całym słownikiem?

Jeśli dobrze ogarniam to:

  • jesli słownik jest drzewem binarnym zrównoważonym to mamy log(4*1000*1000)/log(2) czyli około 22 porównania
  • jesli słownik jest tablicą haszującą to pewnie mamy coś koło 1 (słownie jeden) porównania

Więc o co chodzi bo nie rozumiem?

4

Ty o tym myślisz w kontekście Twojego jednego projektu w którym potrzebujesz porównać sobie słowa, i implementacja w PHP jest zbyt wolna, i nie wiesz jak ją przyspieszyć.

Więc stworzyłeś Issue, z prośbą o to żeby ktoś inny niż Ty (jakiś dev w PHP) to zaimplementował na wszystkich wspieranych platformach (skoro ma być dodane do języka), oraz na wszystkich wspieranych wersjach PHP, i jednocześnie prosisz (niejawnie) o to żeby ta funkcja była utrzymywana we wszystkich późniejszych wersjach języka.

Czy Ty jesteś poważny? Nie masz pojęcia jak dużym przedsięwzięciem jest dodanie takiej funkcjonalności do takiego rozwiniętego języka, względem Twojego projektu. Nie zdziwię się jak to issue zostanie zamknięte bez podania przyczyny w ciągu paru dni, albo zostanie bez odpowiedzi.

Weź się zastanów o konsekwencjach tego co proponujesz:

  • Dodanie funkcji nawet do biblioteki, pod jeden projekt to jest czasem za dużo pracy;
  • Dodanie funkcji pod jeden projekt do frameworka, takiego jak Laravel to jest za dużo pracy - za dużo wersji i platform do wspierania, za dużo konsekwencji dla tysięcy użytkowników którzy tego używają.
  • A Ty chcesz dodać nową funkcję do całego języka pod Twój jeden projekt?

Jeśli ciągle mało argumentów, to:

  • Dodatkowo, jak już mówiono, możesz sam napisać taki extension w C, i skompilować to do .dll lub innego formatu, i po prostu użyć w swoim projekcie. Czemu tego nie zrobisz?
  • Jak nie chcesz tego robić, to drugim najmniej inwazyjnym krokiem byłoby zrobienie forka php-src, i napisanie w nim samemu funkcji mb_levenshtein i skompilowanie takiego PHP u siebie, żeby pokazać w ogóle POC. Gdybyś to zrobił sam, to wiedziałbyś że taki kod najpewniej out-of-the-box zadziała tylko na jednej wersji PHP i pewnie tylko na jednej platformie, na tej której go napisałeś. Musiałbyś włożyć dodatkowy wysiłek żeby działała na innych platformach oraz na wszystkich wersjach PHP + oraz aktualizować ją, jak pojawiają się nowe wersje PHP, nie mówiąc o napisaniu odpowiednich testów automatycznych pod to.
  • I o to wszystko prosisz devów PHP zakładając takie Issue. Jak myślisz, jak na to zareagują?

Prezentujesz typową postawę "zróbcie wszystko za mnie, bo ja chcę".

PS: Sprawdzałeś to?

0
KamilAdam napisał(a):
jurek1980 napisał(a):

ale trzeba nieznane słowa porównać z prawie 4 milionami słów w j. polskim.

Każde nieznane słowo porównujesz z całym słownikiem?

Jeśli dobrze ogarniam to:

  • jesli słownik jest drzewem binarnym zrównoważonym to mamy log(4*1000*1000)/log(2) czyli około 22 porównania
  • jesli słownik jest tablicą haszującą to pewnie mamy coś koło 1 (słownie jeden) porównania

Mam słownik z około 4 milionami słów j. polskiego i mam tekst do sprawdzenia, każde słowo tekstu porównuje ze słownikiem. Następnie nierozpoznane słowa, np. z literówkami typu "powaracają", porównuje ponownie z całym słownikiem tym razem robiąc levenshteina, tam gdzie wynik wynosi 20% lub mniej długości słowa (1 dla wyrazów krótszych niż 8) tam dodaje to słowo jako propozycję korekcji.

Tutaj wynik dla 4 różnych nierozpoznanych słów, klucz = nierozpoznane słowo, wartość - tablice propozycji.

W miarę dobrze to działa, bo dla każdej propozycji robię jeszcze dodatkowo levenshtaina poprawionego w implementacji PHP z multibyte (np. dla "powaracają", "powracają" ma najpierw wynik 2 po korekcji 1), ale problem pojawia się kiedy do korekcji jest więcej niż jeden znak diakrytyczny, czyli np. jest "zolnierska" zamiast "żołnierska" - bo wtedy wynik z levenshteina bez multibyte wychodzi ponad 2 i nie jest to wstępną propozycją, tym samym nie robię potem korekcji żeby otrzymać wynik 2.

Array
(
    [Bolesnie] => Array
        (
            [bolesne] => 1
            [bolenie] => 1
            [boleśnie] => 1
            [blednie] => 2
            [bolasie] => 2
            [boldynie] => 2
            [bolejcie] => 2
            [boleni] => 2
            [bolenia] => 2
            [boleniem] => 2
        )

    [istnieja] => Array
        (
            [istniej] => 1
            [istnieją] => 1
            [istnieje] => 1
            [istnieję] => 1
            [istnej] => 2
            [istnie] => 2
            [istnieć] => 2
            [istniejmy] => 2
            [istnieli] => 2
            [istnienia] => 2
        )

    [Klepsydrzę] => Array
        (
            [klepsydrę] => 1
            [klepsydrze] => 1
            [klepsydrą] => 2
        )

    [powaracają] => Array
        (
            [powracają] => 1
            [poharatają] => 2
            [ponawracają] => 2
            [poobracają] => 2
            [poskracają] => 2
            [powracając] => 2
            [powytracają] => 2
            [powywracają] => 2
            [pozatracają] => 2
            [pozawracają] => 2
        )

)
0
TomRZ napisał(a):

Mam słownik z około 4 milionami słów j. polskiego i mam tekst do sprawdzenia, każde słowo tekstu porównuje ze słownikiem. Następnie nierozpoznane słowa, np. z literówkami typu "powaracają", porównuje ponownie z całym słownikiem tym razem robiąc levenshteina, tam gdzie wynik wynosi 20% lub mniej długości słowa (1 dla wyrazów krótszych niż 8) tam dodaje to słowo jako propozycję korekcji.

Tutaj wynik dla 4 różnych nierozpoznanych słów, klucz = nierozpoznane słowo, wartość - tablice propozycji.

W miarę dobrze to działa, bo dla każdej propozycji robię jeszcze dodatkowo levenshtaina poprawionego w implementacji PHP z multibyte, ale problem pojawia się kiedy do korekcji jest więcej niż jeden znak diakrytyczny, czyli np. jest "zolnierska" zamiast "żołnierska" - bo wtedy wynik z levenshteina bez multibyte wychodzi ponad 2 i nie jest to wstępną propozycją, tym samym nie robię potem korekcji żeby otrzymać wynik 2.

A nie możesz w pierwszym obejściu, jak porównujesz te 4 miliony słów usuwać z nich znaki diaryktyczne i zrobić "pierwszy odsiew" tych które na pewno nie pasują, i potem dopiero drugi raz na mniejszej ilości słów zrobić swojego "multibyte levenstein"?

0
Riddle napisał(a):
TomRZ napisał(a):

A nie możesz w pierwszym obejściu, jak porównujesz te 4 miliony słów usuwać z nich znaki diaryktyczne i zrobić "pierwszy odsiew" tych które na pewno nie pasują, i potem dopiero drugi raz na mniejszej ilości słów zrobić swojego "multibyte levenstein"?

Ta pierwsza iteracja to nie jest problem, bo tam nie ma levenshteina tylko proste porównanie czy słowo istnieje. Problemem jest sam levenshtein, kiedy mam już niepasujące słowo i porównuje z każdym ze słownika, substytucja np. "a" na "e" = 1, dobrze, ale np. "a" na "ą" daje już wynik 2, czyli źe bo powinno być 1. Implementacja w czystym PHP daje 1, ale jest kilkadziesiąt razy wolniejsza. Może później wieczorem wrzucę tutaj klasę / funkcję która to robi plus adres do słownika, to każdy się będzie mógł pobawić.

1

Ja bym odsiał jeszcze słowa co najmniej po długości.
Po co porównywać kot z powaracają? Nie jestem dobry w algorytmy i zaraz wyjdzie, że na to są jakieś gotowce.

0
TomRZ napisał(a):
Riddle napisał(a):
TomRZ napisał(a):

A nie możesz w pierwszym obejściu, jak porównujesz te 4 miliony słów usuwać z nich znaki diaryktyczne i zrobić "pierwszy odsiew" tych które na pewno nie pasują, i potem dopiero drugi raz na mniejszej ilości słów zrobić swojego "multibyte levenstein"?

Ta pierwsza iteracja to nie jest problem, bo tam nie ma levenshteina tylko proste porównanie czy słowo istnieje. Problemem jest sam levenshtein, kiedy mam już niepasujące słowo i porównuje z każdym ze słownika, substytucja np. "a" na "e" = 1, dobrze, ale np. "a" na "ą" daje już wynik 2, czyli źe bo powinno być 1. Implementacja w czystym PHP daje 1, ale jest kilkadziesiąt razy wolniejsza. Może później wieczorem wrzucę tutaj klasę / funkcję która to robi plus adres do słownika, to każdy się będzie mógł pobawić.

Nie rozumiesz co napisałem.

Nie zaczynaj od powrównywania levensteinem.

Napisz sobie funkcje

function stupid_levenstein(string $string1, string $string2) {
  $stupid1 = \str_replace(['ą', 'ę', 'ł', 'ś', 'ć', 'ź'], ['a', 'e', 'l', 's', 'c', 'z'], $string1);
  $stupid2 = \str_replace(['ą', 'ę', 'ł', 'ś', 'ć', 'ź'], ['a', 'e', 'l', 's', 'c', 'z'], $string2);
  return levenstein($stupi1, $stupid2);
}

I najpierw porównaj tą funkcją wszystkie 4 miliony słów, odsiejesz w ten sposób znaczną ilość słów które na pewno nie pasują, a działa szybko. Dostaniesz wtedy mniejszy zbiór słów do sprawdzenia, i na tym zbiorze potem użyj swojej "multibyte levenstein". Rozwiązanie właściwie tożsame z odpowiedzą @katakrowa.

Plus, podesłałem Ci trzy linki, sprawdziłeś je?

0

Tu jeszcze trzeba wyjść poza reprezentację ASCII.
Mamy przypadki polskich słów jak grzegżółka gdzie przy dużej liczbie ortografów levenstein po konwersji do ASCII może dawać złe podpowiedzi. Trzeba by to przetestować.

0
jurek1980 napisał(a):

Tu jeszcze trzeba wyjść poza reprezentację ASCII.
Mamy przypadki polskich słów jak grzegżółka gdzie przy dużej liczbie ortografów levenstein po konwersji do ASCII może dawać złe podpowiedzi. Trzeba by to przetestować.

Dlatego właśnie spłaszczanie znaków diakrytycznych do zwykłych, czyli to co proponuje @Riddle poprzez linki, to niestety nie jest dobre rozwiązanie. Teraz pracuję i nie mam czasu, ale wieczorem wrzucę jeszcze poprawioną funkcję na Githuba i tutaj każdy zainteresowany będzie się mógł pobawić i to ulepszyć.

1
TomRZ napisał(a):
jurek1980 napisał(a):

Tu jeszcze trzeba wyjść poza reprezentację ASCII.
Mamy przypadki polskich słów jak grzegżółka gdzie przy dużej liczbie ortografów levenstein po konwersji do ASCII może dawać złe podpowiedzi. Trzeba by to przetestować.

Dlatego właśnie spłaszczanie znaków diakrytycznych do zwykłych, czyli to co proponuje @Riddle poprzez linki, to niestety nie jest dobre rozwiązanie. Teraz pracuję i nie mam czasu, ale wieczorem wrzucę jeszcze poprawioną funkcję na Githuba i tutaj każdy zainteresowany będzie się mógł pobawić i to ulepszyć.

Nadal nie rozumiesz.

Chodzi o to żeby najpierw spłaszczyć słowa (grzegżółka -> grzegzolka), i w ten sposób "prostym levensteinem" odsiać te które nie pasują już na początku, i tym samym zmniejszyć rozmiar słownika - a potem na niespłaszonych słowach, czyli grzegżółka przejechać "multibyte levensteinem" żeby zawęzić wyniki tylko do tych poprawnych. Operowanie na spłaszczonym stringu ma być tylko pośrednim krokiem, mającym na celu zmniejszenie wielkości słownika do przeszukania, z 4 milionów do prawdopodobnie rzędy wielkości mniejszego.

Nie wiem jak bardziej opisowo mogę to napisać:

function flatWord(string $word) {
  // funkcja która zamienia znaki diaryktyczne na proste litery
}

function stupid_levenshtein(string $s1, string $s2) {
  return levenstein(flatWord($s1), flatWord($s2));
}

$wielkiSłownik = [
  // 4 miliony słów
]; 
$szukaneSłowo = "grzegżółka";

$malySlownik = [];
foreach ($wielkiSłownik as $slowo) {
  if (stupid_levenshtein($slowo, $szukaneSlowo) < X) {  // pierwsze przeszukanie, używając płaskich słów
    $malySlownik[] = $slowo;
  }
}

$result = [];
foreach ($malySlownik as $word) {
  if (multibyte_levenstein($slowo, $word) < X) {  // dokładne przeszukanie, na mniejszym zbiorze
    $result[] = $word;
  }
}

Możesz to jeszcze bardziej zoptymalizować, i za wczasu zbudować sobie osobny plik z płaskimi słowami, żeby nie musieć ich spłaszczać co każdy request. Jak widzisz pole do popisu z optymalizacją jest duże. Możesz też to zrobić w tej samej pętli - jeśli jakieś słowo nie przechodzi stupid_levenshtein(), to tym bardziej nie przejdzie multibyte_levenstein().

Tak jak zgadzam się że mb_levenstein() byłoby dobrym pomysłem żeby go dodać do języka, tak Twoje powody żeby go dodać są całkowicie absurdalne.

0

Dobrze, ale teraz pytanie ile pamięci zajmowałby ten mniejszy słownik. Większy to oczywiście jazda linia po linii pliku słownika, żeby go nie ładować całego do pamięci, ale taki mniejszy słownik musiałby być już cały załadowany. Pobawię się wieczorem i zobaczymy.

0
TomRZ napisał(a):

Dobrze, ale teraz pytanie ile pamięci zajmowałby ten mniejszy słownik. Większy to oczywiście jazda linia po linii pliku słownika, żeby go nie ładować całego do pamięci, ale taki mniejszy słownik musiałby być już cały załadowany. Pobawię się wieczorem i zobaczymy.

Przecież Ci napisałem:

Riddle napisał(a):

Możesz też to zrobić w tej samej pętli - jeśli jakieś słowo nie przechodzi stupid_levenshtein(), to tym bardziej nie przejdzie multibyte_levenstein().

Czytaj posty ze zrozumieniem.

0

Błędy w słowach to też często przestawienie liter, dodanie zbędnej litery, ale najrzadziej robimy błąd w pierwszej literze słowa. No może jak słownik podpowie coś zupełnie źle.
Także kolejny odsiew to ograniczenie sprawdzania słów zaczynających się od danej litery. I tak redukujemy słownik znacznie. Wykonując później porównania nawet w pętli będzie znaczenie łatwiej.

0
jurek1980 napisał(a):

Błędy w słowach to też często przestawienie liter, dodanie zbędnej litery, ale najrzadziej robimy błąd w pierwszej literze słowa. No może jak słownik podpowie coś zupełnie źle.
Także kolejny odsiew to ograniczenie sprawdzania słów zaczynających się od danej litery. I tak redukujemy słownik znacznie. Wykonując później porównania nawet w pętli będzie znaczenie łatwiej.

Na pewno można zrobić różne optymalizacje, ja dopiero wczoraj wieczorem napisałem tę funkcję, a dzisiaj wieczorem ją wrzucę na Githuba, na pewno będzie ją można ulepszyć. Myślę, że to rzecz która przyda się nie tylko dla mnie, ale dla wielu ludzi piszących teksty do internetu, gdzie np. z jakichś powodów podświetlenie błędów przez przeglądarkę to za mało lub z jakiegoś powodu jest niedostępne.

0

Dodałem repozytorium:

https://github.com/tztztztz/PHP-Spell-Checker-And-Substitution-Suggester

W Readme pisze skąd ściągnąć słownik, nie chciałem go umieszczać w repo.

Na pewno można to zoptymalizować na różne sposoby.

Poza tym co było pisane w tym wątku do głowy przychodzi mi:

  • stworzenie indeksu b-tree dla rozpoznania nieistniejących słów, zamiast męczenie linia po linii słownika
  • obsługa wielowątkowości - czyli podział pracy na kilka wątków

Zainteresowanych zapraszam do testowania i ulepszania, na razie do webu średnio się to nadaje bo na moim procku (AMD 5800X), test który jest zawarty w repo wykonuje się w trochę ponad 6 sekund... trochę za wolno jak dla mnie przy edycji tekstów w jakimś administratorze systemu internetowego, chociaż dało by się przeżyć nawet tą wersję teraz.

Ja ze swojej strony się z tym nie spieszę, ale jeżeli nikt tam nic nie poprawi i nie ulepszy to pewnie w następnych tygodniach powoli coś tam będę grzebał. Za niedługo dodam też na to licencję MIT jakby co.

W teście widać, że z sugestią dla słowa "wciąz" jest problem, a jeszcze większy kiedy jest "wciaz". Tego typu krótkie słowa to jest wyzwanie aby zrobić to bez podstawowego levenshteina obsługującego mbstringi.

0
TomRZ napisał(a):

Dodałem repozytorium:

https://github.com/tztztztz/PHP-Spell-Checker-And-Substitution-Suggester

No jakościowo to ten kod to jest dno.

U mnie ten kod testowy wykonuje się 9 sekund, nie wiem czy tak ma być?

0

Ależ oczywiście że dno, jakiej innej opinii bym się po Tobie spodziewał? :) Na szczęście mam ją gdzieś. No ale zawsze może to zrobić lepiej - o ile potrafisz, w co wątpię.

1
TomRZ napisał(a):

Ależ oczywiście że dno, jakiej innej opinii bym się po Tobie spodziewał? :) Na szczęście mam ją gdzieś. No ale zawsze może to zrobić lepiej - o ile potrafisz, w co wątpię.

No biorąc pod uwagę całkowity brak testów, funkcja na 125 linijek, niepoprawne nazwy po angielsku, zmienne typu $p, $c1, $c2, $fp, $fp2, funkcje statyczne nie wiadomo po co, raz nazwy camelCase raz snake_case, nie mówiąc już o wczytywaniu z plików wymieszane z logiką; to faktycznie jest się czym chwalić.

0

Spoko, masz rację, tylko to jest wersja 0.0.1 wczesna alfa a nie 1.0, a wszystko pisane na szybko. Rozumiem jednak, że masz po prostu taką potrzebę pisać to co piszesz, ale nie wiem czy zdajesz sobie sprawę, że to bardziej Twój problem, niż mój :) Ja w każdym razie na dzisiaj stąd znikam, bo mam lepsze rzeczy do robienia pa.

1

No ale wracając do meritum - widzisz, wystarczyło tylko odfiltrować większość słów zwykłym levenshtein() i żadne petycje do PHP nie są potrzebne :>

Czas spadł z 7:45 min do ledwo 9 sekund.

0

Nie rozumiesz na czym tutaj polega problem, albo udajesz, że nie rozumiesz. Nadal potrzebna jest taka funkcja, żeby pierwsza punktacja była odpowiednia, ale po co ja to tłumacze, przecież tobie nie chodzi o to żeby tutaj cokolwiek poprawić.

1
TomRZ napisał(a):

Nie rozumiesz na czym tutaj polega problem, albo udajesz, że nie rozumiesz. Nadal potrzebna jest taka funkcja, żeby pierwsza punktacja była odpowiednia, ale po co ja to tłumacze, przecież tobie nie chodzi o to żeby tutaj cokolwiek poprawić.

Ale taką funkcję możesz sobie sam napisać, nie musisz pisać żadnych petycji żeby dodać ją do języka.

Nawet dostałeś 3 linki gdzie szukać pomocy:

Poza tym, całkowicie olałeś sugestię od @katakrowa żeby zamienić znaki diaryktyczna na codepoint, i używać nadal zwykłego levenshtein(), a to również drastycznie przyspieszyłoby całość.

No i nie wspominając o tym, że spora część czasu w Twojej aplikacji nie schodzi wcale na liczenie levenshteina tylko na iterację po tym 3 milionowym słowniku - raz żeby sprawdzić czy słowo istnieje, i drugi raz żeby znaleźć wszystkie dopasowania. Dodatkowo, Ty iterujesz po nim linijka po linijce, a mógłbyś iterować np po kilka kilobajtów na raz, i potem dynamicznie w PHP robić splita po nowych liniach, zapamiętać ostatnie ucięte słowo, i iterować dalej. Im większy chunk na raz tym trochę więcej pamięci PHP zje, ale szybciej to przejedzie. Teraz Twoja apka zjada 450Kb i 9 sekund szukania; jak wczytasz cały słownik na raz to wtedy zjada około 200Mb; gdzieś pomiędzy tymi liczbami może być złoty środek.

Wcześniej - zanim posłuchałeś mojej rady żeby użyć zwykłego bajtowego levenshtein()a zanim użyjesz swojego "multibyte" to owszem, spora część z tych 7 minut szła na liczenie odległości słów od siebie - ale teraz już nie.

0

Ale taką funkcję używam już w kodzie, w momencie kiedy pierwsza funkcja wbudowana zwróci odpowiednio niską punktację - wtedy używam dodatkowo tej z php obsługującej multibyte

Tymczasem mając wbudowaną funkcję od razu w php mogę od razu dostać prawidłową punktację.

Po drugie przecież wyraźnie napisałem tutaj i w readme, że potrzebuje to kolejnych optymalizacji: czyli zbudowania indeksu b-tree oraz rozłożenia na kilka wątków, a Ty tu wpisujesz rzeczy jakbyś w ogóle tego nie przeczytał. Zapętlasz się i w kółko piszesz to samo.

Po trzecie nie martw się tak bardzo petycją, dostałem już odpowiedź do deweloperów PHP że to dobry pomysł i będą implementować. No ale możesz tam napisać i się poskarżyć, że Tobie to bardzo przeszkadza, i żeby nie robili xD

0
TomRZ napisał(a):

Ale taką funkcję używam już w kodzie, w momencie kiedy pierwsza funkcja wbudowana zwróci odpowiednio niską punktację - wtedy używam dodatkowo tej z php obsługującej multibyte

No to chyba wszystko jest git, nie? I już po sprawie.

Chyba że masz ochotę jeszcze dalej próbować optymalizować swoje rozwiązanie, to ja proponuję użyć tego co napisał @katakrowa i zastąpić znaki diratyktyczne codepointami, to jest najprostsze a zarazem może dać znaczący wynik.

TomRZ napisał(a):

Tymczasem mając wbudowaną funkcję od razu w php mogę od razu dostać prawidłową punktację.

I byłoby to lepsze... czemu? Efekt w Twojej aplikacji i tak będzie taki sam.

Nie potrzebujesz do niczego tej funkcji, a nawet jakbyś faktycznie potrzebował, to @cmb69 odpisał w Twojej petycji że jeśli koniecznie tego potrzebujesz, to lepiej stworzyć extension pod swoje potrzeby (https://github.com/php/php-src/issues/10180#issuecomment-1367280085) - dokładnie to co napisali Ci forumowicze tutaj.

TomRZ napisał(a):

Po drugie przecież wyraźnie napisałem tutaj i w readme, że potrzebuje to kolejnych optymalizacji: czyli zbudowania indeksu b-tree oraz rozłożenia na kilka wątków, a Ty tu wpisujesz rzeczy jakbyś w ogóle tego nie przeczytał. Zapętlasz się i w kółko piszesz to samo.

Przeczytałem, ale to wszystko jest bardzo odwrotne.

Stworzyłeś rozwiązanie które wykonuje się jakieś 5 minut, stwierdziłeś że za długo, i Twoim pomysłem było dodanie nowej funkcji do całego języka, a kolejnymi pomysłami było parallelizacja rozwiązania i model drzewa; ale nie wpadłeś na to żeby użyć już istniejącej funkcji żeby odsiać 99% słów z Twoich trzech milionów.

TomRZ napisał(a):

Po trzecie nie martw się tak bardzo petycją, dostałem już odpowiedź do deweloperów PHP że to dobry pomysł i będą implementować. No ale możesz tam napisać i się poskarżyć, że Tobie to bardzo przeszkadza, i żeby nie robili xD

No, z tego co widzę to dostałeś jedną odpowiedź od zwykłego użytkownika, oraz odpowiedź od @cmb69 że bez RFC nic nie zrobią.

0
Riddle napisał(a):
TomRZ napisał(a):

Ale taką funkcję używam już w kodzie, w momencie kiedy pierwsza funkcja wbudowana zwróci odpowiednio niską punktację - wtedy używam dodatkowo tej z php obsługującej multibyte

No to chyba wszystko jest git, nie? I już po sprawie.

Chyba że masz ochotę jeszcze dalej próbować optymalizować swoje rozwiązanie, to ja proponuję użyć tego co napisał @katakrowa i zastąpić znaki diratyktyczne codepointami, to jest najprostsze a zarazem może dać znaczący wynik.

TomRZ napisał(a):

Tymczasem mając wbudowaną funkcję od razu w php mogę od razu dostać prawidłową punktację.

I byłoby to lepsze... czemu? Efekt w Twojej aplikacji i tak będzie taki sam.

Nie.

Po pierwsze nie muszę korygować punktacji levenshtaina zrobionej bez multibyte na tą z multibyte, żeby ją obniżyć i podwyższyć w rankingu propozycji - ale to mniejszy problem.

Większy problem jest kiedy w słowie są dwa lub więcej znaki diakrytyczne "spłaszczone" (np. a zamiast ą i e zamiast ę) i levenshtain bez multibyte zwraca tak wysoki wynik, że nawet nie uwzględnię tego w propozycjach, czyli mam np. 4 punktu zamiast 2, a próg propozycji to 3.

Mając od razu wbudowanego levenshteina z multibyte od razu mam 2 punkty i umieszczam to w propozycjach, a tak to mam do wyboru tracić takie propozycje albo podwyższyć próg punktacji levenshtaina dla uwzględnienia propozycji, co powoduje duże obniżenie wydajności, bo o wiele więcej muszę analizować / korygować funkcją w czystym PHP, która jest bardzo wolna.

Dlatego taka funkcja jest potrzebna tutaj.

TomRZ napisał(a):

Po drugie przecież wyraźnie napisałem tutaj i w readme, że potrzebuje to kolejnych optymalizacji: czyli zbudowania indeksu b-tree oraz rozłożenia na kilka wątków, a Ty tu wpisujesz rzeczy jakbyś w ogóle tego nie przeczytał. Zapętlasz się i w kółko piszesz to samo.

Przeczytałem, ale to wszystko jest bardzo odwrotne.

Stworzyłeś rozwiązanie które wykonuje się jakieś 5 minut, stwierdziłeś że za długo, i Twoim pomysłem było dodanie nowej funkcji do całego języka, a kolejnymi pomysłami było parallelizacja rozwiązania i model drzewa; ale nie wpadłeś na to żeby użyć już istniejącej funkcji żeby odsiać 99% słów z Twoich trzech milionów.

Nie, moje pierwsze rozwiązanie to była wbudowana funkcja, i działało to tak jak teraz 7 sek, potem spróbowałem to robić implementacją w PHP i zrobiło się kilka minut.

To będzie działać optymalnie kiedy:

  • z prostego słownika w pliku linia po linii, zrobi się index b-tree i w ten sposób będzie się wykrywać nieistniejące słowa
  • będzie wbudowana funkcja mb_levenshtein
  • praca będzie mogła być podzielona na kilka wątków

Wtedy to będą ułamki sekund aby otrzymać propozycje dla tekstu który jest w teście na githubie, a nie 7 sekund jak teraz.

TomRZ napisał(a):

Po trzecie nie martw się tak bardzo petycją, dostałem już odpowiedź do deweloperów PHP że to dobry pomysł i będą implementować. No ale możesz tam napisać i się poskarżyć, że Tobie to bardzo przeszkadza, i żeby nie robili xD

No, z tego co widzę to dostałeś jedną odpowiedź od zwykłego użytkownika, oraz odpowiedź od @cmb69 że bez RFC nic nie zrobią.

Dobrze, ale napisał, że to dobry pomysł, i nie odrzucił tego.

0
TomRZ napisał(a):
TomRZ napisał(a):

Po trzecie nie martw się tak bardzo petycją, dostałem już odpowiedź do deweloperów PHP że to dobry pomysł i będą implementować. No ale możesz tam napisać i się poskarżyć, że Tobie to bardzo przeszkadza, i żeby nie robili xD

No, z tego co widzę to dostałeś jedną odpowiedź od zwykłego użytkownika, oraz odpowiedź od @cmb69 że bez RFC nic nie zrobią.

Dobrze, ale napisał, że to dobry pomysł, i nie odrzucił tego.

No to super, to czekam na PHP 8.3 z mb_levenshtein().

1 użytkowników online, w tym zalogowanych: 0, gości: 1