Próbuję napisać (idealną) tablicę asocjacyjną do kompresji mapowania z unicode codepoint names to their codepoint number (odwzorowanie drugiej kolumny do pierwszej kolumny). Jak widzisz, możliwe dane wejściowe są bardzo ograniczone, w rzeczywistości w alfabecie jest dokładnie 38 znaków: AB...YZ, 0...9, - i przestrzeń. Ponadto istnieje wiele powtórzeń (substring), DIGIT ZERO, DIGIT ONE, ..., LATIN CAPITAL LETTER A, LATIN CAPITAL LETTER B itpEfektywna funkcja skrótu dla łańcuchów alfanumerycznych o niskiej entropii
Idealne tabeli mieszania jest obliczana poprzez wybór materiału siewnego S, a następnie próbuje skonstruować doskonałą tabeli mieszania zaszczepienie (w pewien sposób) hasher'a przez S. Jeśli nie można utworzyć tabeli, ponawia próbę z nowym początkiem. Posiadanie wielu kolizji zazwyczaj wymaga więcej prób, ponieważ algorytm jest trudniejszy do dopasowania.
Efektem tego jest moja domena wejściowa ma niską entropię, a tworzenie tabeli wymaga wielu prób z prostymi funkcjami skrótu, takimi jak DJB2; lepsze półki, takie jak FNV, działają dobrze, ale bardziej skomplikowane i wolniejsze funkcje, takie jak SipHash, wydają się wymagać mniejszej liczby ponownych prób.
Ponieważ jest to całkowicie statyczne i prekomputowane, nie martwię się zbytnio jakością dla jakości (tj. Bezpieczeństwo i rozkład probabilistyczny dla dowolnych danych wejściowych w czasie wykonywania nie ma znaczenia), ale funkcje wyższej jakości skracają wymagany czas wstępnego obliczania dla danego poziomu kompresji, odwrotnie, pozwól mi osiągnąć wyższą kompresję w pewnym ustalonym czasie.
Pytanie: czy istnieją wydajne opublikowane funkcje skrótu dostosowane do danych wejściowych z takimi ograniczeniami domenowymi? To znaczy, czy istnieją funkcje mieszania, które wykorzystują dodatkową strukturę do wykonywania mniejszej liczby operacji, ale nadal osiągają rozsądne wyniki?
Szukałem takich rzeczy jak "alfanumeryczna funkcja skrótu", ale wyniki nie są powiązane (w większości po prostu generowanie ciągów alfanumerycznych jako wyniku działania funkcji skrótu); nawet wskazówki dotyczące właściwego żargonu, aby móc wyszukiwać dokumenty byłyby pomocne.
(To pytanie jest motywowane jest nieco ciekawe rozwiązania, w rzeczywistości nie jest to konieczne.)
Potrzebujesz idealnego skrótu dla 27268 elementów? Wydaje mi się trudne. Dlaczego nie skorzystać z * standardowej * funkcji skrótu i obsługi kolizji? (i może użyjemy niskiego współczynnika wypełnienia) – wildplasser
@wildplasser działa dobrze, może zająć trochę czasu, aby wygenerować. Na przykład. [ta tablica] (https://github.com/huonw/unicode_names/blob/1f331f78201b914604346e1d6fc3e9b3b2eda772/src/generated_phf.rs # L771) jest samym hashtable: użyj skrótu wejściowego łańcucha jako indeksu do tej tabeli (a następnie sprawdź, czy jest poprawna). Chodzi o to, aby struktura danych wejściowych była szybsza, wykonując jak najmniej pracy. Ma to również na celu kompresję, więc współczynnik niskiego obciążenia nie jest dobry. – huon
@wildplasser Na koniec zauważ, że obecnie używam standardowej funkcji skrótu (w rzeczywistości wspomniałem trzy w pytaniu). – huon