Jak najszybciej wyszukać anagramy? Mam słownik 100-200 tyś słów, i
kolejne słowa próbuję.
Może tak, że słownik przestawię w postaci pary - słowa posortowanego,słowa?
np.
abcino,bocian
?

do góry

W dniu 04.04.2016 o 17:20, Borneq pisze:
> Jak najszybciej wyszukać anagramy? Mam słownik 100-200 tyś słów, i
> kolejne słowa próbuję.
> Może tak, że słownik przestawię w postaci pary - słowa posortowanego,słowa?
> np.
> abcino,bocian
> ?
Tylko jak to sortować?, sortowanie kubełkowe? czy to sortowanie nie
stwarza problemów, gdy jakaś litera się powtarza, Kubełków mogło by byc
mało dla ASCII, ale trzeba by dużej liczby dla Unicodu

do góry

Najlepiej przy pomocy algorytmu genetycznego - żart.

Ja bym sprobował hashtable i funkcji skrótu odpornej na kolejność znakow.

do góry

W dniu 2016-04-04 o 17:20, Borneq pisze:
> Jak najszybciej wyszukać anagramy? Mam słownik 100-200 tyś słów, i
> kolejne słowa próbuję.
> Może tak, że słownik przestawię w postaci pary - słowa posortowanego,słowa?
> np.
> abcino,bocian

Czy słowo "abcino" występuje w tym słowniku (zakładam, że "bocian"
istnieje)? Czy może "abcino" to losowy ciąg liter i w tym słowniku
chcesz sprawdzić czy istnieje "anagram" dla takich liter?
(Bo o ile kojarzę, anagram to słowo powstałe w wyniku przestawienia
liter z innego słowa - oba sensowne. Bo w innym przypadku dla dowolnego
słowa liczysz możliwe dowolne kombinacje ustawienia liter i masz ilość
"anagramów", które potencjalnie mogą wystąpić w słowniku...)
Czyli inaczej pytając, chcesz znaleźć konkretny anagram (anagramy), czy
wszystkie istniejące w słowniku?
Nie znam słowa "abcino" stąd pytanie o doprecyzowanie, bo od tego chyba
zależy dalszy sposób szukania.

Oczywiście nie znam odpowiedzi :) ale skoro to grupa dyskusyjna to
pomyślałem, że zacząłbym od pogrupowania elementów słownika w/g ilości
liter. Pierwszym warunkiem jest to, że słowa-anagramy na pewno mają
dokładnie tę samą ilość liter. I szukałbym anagramu(ów) dla słowa
"bocian" tylko w grupie wyrazów 6cio literowych.

Tak samo, jakbym chciał poznać ilość wszystkich anagramów istniejących w
słowniku, to utworzyłbym tyle wątków wyszukujących, ile jest grup
n-literowych.

Ale już samo wyszukiwanie w poszczególnych grupach to się nie
zastanawiałem (w sensie szybkości, bo zliczanie liter i porównywanie
wystąpień z kolejnym wyrazami raczej jest banalne i do zrobienia na
piechotę, tyle że pewnie da się zastosować jakąś magię i ktoś mądrzejszy
już ją zna ;)

Pozdrawiam
Piotr

do góry

W dniu 04.04.2016 o 17:52, M.M. pisze:
> Najlepiej przy pomocy algorytmu genetycznego - żart.
>
> Ja bym sprobował hashtable i funkcji skrótu odpornej na kolejność znakow.
>
Fakt, to może być jeszcze szybsze

do góry

W dniu 04.04.2016 o 18:16, Kviat pisze:
> Czy słowo "abcino" występuje w tym słowniku (zakładam, że "bocian"
> istnieje)? Czy może "abcino" to losowy ciąg liter i w tym słowniku
> chcesz sprawdzić czy istnieje "anagram" dla takich liter?

Właśnie, jest tu pewien problem: mamy w słowniku akr i rak, kra. Dla
słowa akr hasz znajdzie mi tylko jeden, poza tym byłby chyba błąd przy
dodawaniu takich samych haszy. To jest zależne od języka, prawdopodobnie
w C# ale nie jestem pewien

do góry

W dniu 2016-04-04 o 18:25, Borneq pisze:
> W dniu 04.04.2016 o 18:16, Kviat pisze:
>> Czy słowo "abcino" występuje w tym słowniku (zakładam, że "bocian"
>> istnieje)? Czy może "abcino" to losowy ciąg liter i w tym słowniku
>> chcesz sprawdzić czy istnieje "anagram" dla takich liter?
>
> Właśnie, jest tu pewien problem: mamy w słowniku akr i rak, kra. Dla
> słowa akr hasz znajdzie mi tylko jeden, poza tym byłby chyba błąd przy
> dodawaniu takich samych haszy. To jest zależne od języka, prawdopodobnie
> w C# ale nie jestem pewien

Właśnie na szybko coś takiego znalazłem:
https://www.rosettacode.org/wiki/Anagrams
Może Ci się przyda.

Pozdrawiam
Piotr

do góry

On Mon, 4 Apr 2016 17:20:59 +0200, Borneq wrote:

> Jak najszybciej wyszukać anagramy? Mam słownik 100-200 tyś słów, i
> kolejne słowa próbuję.
> Może tak, że słownik przestawię w postaci pary - słowa posortowanego,słowa?
> np.
> abcino,bocian
> ?

Każde słowo w słowniku zamieniasz wg algorytmu:

litera[licznik]litera[licznik]

czyli np.:

obrazek: o[1]b[1]r[1]a[1]z[1]e[1]k[1]

teraz sortujesz po alfabecie:

obrazek: a[1]b[1]e[1]k[1]o[1]r[1]z[1]

i tak lecisz po całym słowniku.

A potem sortujesz słownik wg tego "hasza".

No i potem masz obok siebie wszystkie anagramy, czyli np. za obrazkiem
jest:

zarobek: a[1]b[1]e[1]k[1]o[1]r[1]z[1]


--
howgh
szemrany
"Zrozumienie umożliwia zastąpienie nieracjonalnych działań lub bezradności
przez działania racjonalne." M.Mazur, ojciec polskiej szkoły cybernetyki

do góry

On Monday, April 4, 2016 at 6:21:51 PM UTC+2, Borneq wrote:
> W dniu 04.04.2016 o 17:52, M.M. pisze:
> > Najlepiej przy pomocy algorytmu genetycznego - żart.
> >
> > Ja bym sprobował hashtable i funkcji skrótu odpornej na kolejność znakow.
> >
> Fakt, to może być jeszcze szybsze

Tak się wydaje, w praktyce mogą wyjść jakieś schody. Warto spróbować
jeśli wydajność jest ważna.

Pozdrawiam

do góry

On Monday, April 4, 2016 at 9:57:05 PM UTC+2, M.M. wrote:
> On Monday, April 4, 2016 at 6:21:51 PM UTC+2, Borneq wrote:
> > W dniu 04.04.2016 o 17:52, M.M. pisze:
> > > Najlepiej przy pomocy algorytmu genetycznego - żart.
> > >
> > > Ja bym sprobował hashtable i funkcji skrótu odpornej na kolejność znakow.
> > >
> > Fakt, to może być jeszcze szybsze
>
> Tak się wydaje, w praktyce mogą wyjść jakieś schody. Warto spróbować
> jeśli wydajność jest ważna.
>
> Pozdrawiam

Sorry że na raty odpisuję. Słowa są krótkie, czyli mają mało liter. Więc
funkcja hash będzie przyjmowała mało wartości, tym bardziej że ma być
odporna na kolejność liter - to są te (potencjalne) schody.

Nie wiem czy warto zrobić taką funkcję hash:

const static unsigned long long hash_keys[256*256] = { rand , rand , rand , etc };

uint mkHash( const char string[] ) {
unsigned long long hash = 0;
for( int i=0 ; string[i] ; i++ ) {
for( int j=i+1 ; string[j] ; j++ ) {
hash ^= hash_keys[ string[i] + string[j] * 256 ];
}
}
return (uint)( hash % hash_size )
}

Pozdrawiam

do góry