Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #28421 > unrolled thread

Masowe wyszukiwanie anagramów

Back to article view | Back to pl.comp.programming

Contents

  Masowe wyszukiwanie anagramów Borneq <borneq@antyspam.hidden.pl> - 2016-04-04 17:20 +0200
    Re: Masowe wyszukiwanie anagramów Borneq <borneq@antyspam.hidden.pl> - 2016-04-04 17:35 +0200
      Re: Masowe wyszukiwanie anagramów "M.M." <mmarszik@gmail.com> - 2016-04-04 08:52 -0700
        Re: Masowe wyszukiwanie anagramów Borneq <borneq@antyspam.hidden.pl> - 2016-04-04 18:21 +0200
          Re: Masowe wyszukiwanie anagramów "M.M." <mmarszik@gmail.com> - 2016-04-04 12:57 -0700
            Re: Masowe wyszukiwanie anagramów "M.M." <mmarszik@gmail.com> - 2016-04-04 13:05 -0700
              Re: Masowe wyszukiwanie anagramów slawek <fake@fakeemail.com> - 2016-04-05 00:17 +0200
      Re: Masowe wyszukiwanie anagramów bartekltg <bartekltg@gmail.com> - 2016-04-05 01:54 +0200
        Re: Masowe wyszukiwanie anagramów "M.M." <mmarszik@gmail.com> - 2016-04-05 05:32 -0700
          Re: Masowe wyszukiwanie anagramów "M.M." <mmarszik@gmail.com> - 2016-04-05 06:28 -0700
    Re: Masowe wyszukiwanie anagramów Kviat <kviat@NIE_DLA_SPAMUneostrada.pl> - 2016-04-04 18:16 +0200
      Re: Masowe wyszukiwanie anagramów Borneq <borneq@antyspam.hidden.pl> - 2016-04-04 18:25 +0200
        Re: Masowe wyszukiwanie anagramów Kviat <kviat@NIE_DLA_SPAMUneostrada.pl> - 2016-04-04 18:49 +0200
    Re: Masowe wyszukiwanie anagramów szemrany <szemrany@offline.off> - 2016-04-04 19:07 +0200

#28421 — Masowe wyszukiwanie anagramów

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
?

[toc] | [next] | [standalone]

#28422

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

[toc] | [prev] | [next] | [standalone]

#28423

Najlepiej przy pomocy algorytmu genetycznego - żart. 

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

[toc] | [prev] | [next] | [standalone]

#28425

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

[toc] | [prev] | [next] | [standalone]

#28438

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

[toc] | [prev] | [next] | [standalone]

#28440

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

[toc] | [prev] | [next] | [standalone]

#28447

Wystarczy wypisać wszystkie słowa w dwu kolumnach, dwa razy obok 
siebie. Litery z pierwszej kolumny posortować wiersz po wierszu. 
Potem posortować wiersze jako klucza używając ciągów znaków z 
pierwszej kolumny. Klasyka.

Pierwsze sortowanie kosztuje O(N) zakładając że ilość liter na słowo 
jest mniejsza niż pewna stała. Drugie to O(N log N). Czyli tyle ma 
cały algorytm.

Pamięciowo jest przyzwoicie: circa 2 razy tyle co słownik.

Hale fun.

[toc] | [prev] | [next] | [standalone]

#28448

On 04.04.2016 17:35, Borneq wrote:
> 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
>> ?

Całkowicie wysatrczy.

> Tylko jak to sortować?,

funckją sort? ;-)


> sortowanie kubełkowe? czy to sortowanie nie
> stwarza problemów, gdy jakaś litera się powtarza,

Nie.

> Kubełków mogło by byc
> mało dla ASCII, ale trzeba by dużej liczby dla Unicodu

Hmm, ciekawostka, patrząc na tabelkę utf-8 traktując
wyrazy jak ciagi bajtów i sortując te bajty nie spowodujesz
niezamierzonej kolizji;-) żadne "ęąń" nie okaże się tym samym ciągiem
co "ółś"


Albo czegoś nie mówisz, albo przekombinowujesz:


#include <vector>
#include <string>
#include <iostream>
#include <algorithm>



using namespace std;


int main()
{

     vector <pair<string, string > > S;
     string str,strs;

     while ( cin>>str )
     {
         strs=str;
         sort(strs.begin(),strs.end());

         S.emplace_back( strs,str );
     }

     sort(S.begin(),S.end());

     for (auto it = S.begin(); it!=S.end();)
     {
         auto itend = next(it);
         while (itend!=S.end() && itend->first == it->first) ++itend;
         if (distance(it, itend)>1)
         {
             cout<<"-- "<<distance(it, itend)<<endl;
             while (it!=itend)
                 cout<<(it++)->second<<endl;

         }
         else it++;
     }

     return 0;
}

Dłużej piszę posta niż pisałem ten kod,
http://sjp.pl/slownik/growy/
2.7 mln słow, 38MB,
time ./untitled <slowa.txt >bla.txt
real	0m5.638s

Nie jest poprawny dla unikodu, ale dzięki uwadze powyżej - działa ;-)

Rekordzista
-- 13
akrom
arkom
kamor
karmo
karom
komar
makro
marko
mokra
morka
okarm
rakom
ramko


pzdr
bartekltg

[toc] | [prev] | [next] | [standalone]

#28449

On Tuesday, April 5, 2016 at 1:54:56 AM UTC+2, bartekltg wrote:
> On 04.04.2016 17:35, Borneq wrote:
> > 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
> >> ?
> 
> Całkowicie wysatrczy.
> 
> > Tylko jak to sortować?,
> 
> funckją sort? ;-)
> 
> 
> > sortowanie kubełkowe? czy to sortowanie nie
> > stwarza problemów, gdy jakaś litera się powtarza,
> 
> Nie.
> 
> > Kubełków mogło by byc
> > mało dla ASCII, ale trzeba by dużej liczby dla Unicodu
> 
> Hmm, ciekawostka, patrząc na tabelkę utf-8 traktując
> wyrazy jak ciagi bajtów i sortując te bajty nie spowodujesz
> niezamierzonej kolizji;-) żadne "ęąń" nie okaże się tym samym ciągiem
> co "ółś"
> 
> 
> Albo czegoś nie mówisz, albo przekombinowujesz:
> 
> 
> #include <vector>
> #include <string>
> #include <iostream>
> #include <algorithm>
> 
> 
> 
> using namespace std;
> 
> 
> int main()
> {
> 
>      vector <pair<string, string > > S;
>      string str,strs;
> 
>      while ( cin>>str )
>      {
>          strs=str;
>          sort(strs.begin(),strs.end());
> 
>          S.emplace_back( strs,str );
>      }
> 
>      sort(S.begin(),S.end());
> 
>      for (auto it = S.begin(); it!=S.end();)
>      {
>          auto itend = next(it);
>          while (itend!=S.end() && itend->first == it->first) ++itend;
>          if (distance(it, itend)>1)
>          {
>              cout<<"-- "<<distance(it, itend)<<endl;
>              while (it!=itend)
>                  cout<<(it++)->second<<endl;
> 
>          }
>          else it++;
>      }
> 
>      return 0;
> }
> 
> Dłużej piszę posta niż pisałem ten kod,
> http://sjp.pl/slownik/growy/
> 2.7 mln słow, 38MB,
> time ./untitled <slowa.txt >bla.txt
> real	0m5.638s
> 
> Nie jest poprawny dla unikodu, ale dzięki uwadze powyżej - działa ;-)
> 
> Rekordzista
> -- 13
> akrom
> arkom
> kamor
> karmo
> karom
> komar
> makro
> marko
> mokra
> morka
> okarm
> rakom
> ramko
> 
> 
> pzdr
> bartekltg

Na hash-table z QT działa z kompilacją 02 na procesorze i3 działa
ciut wolniej:



int main(int argc, char *argv[])
{
    QTextStream in(stdin);
    in.setCodec("UTF-8");
    QString line;
    QMultiHash<QString,QString> hash;

    while( ! ( line = in.readLine() ).isEmpty() ) {
        QString sort = line;
        qSort( sort.begin() , sort.end() );
        hash.insert( sort , line );
    }

    QStringList max;
    QStringList keys = hash.uniqueKeys();
    for( int i=0 ; i<keys.size() ; i++ ) {
        if( max.size() < hash.values( keys[i] ).size() )
            max = hash.values( keys[i] );
    }

    for( int i=0 ; i<max.size() ; i++ )
        printf("%d %s\n",i+1,qPrintable(max[i]));
    fflush(stdout);

    return 0;
}




x@x:~/tmp/build-anagrams-Desktop-Release$ time cat ~/Pobrane/slowa.txt | ./anagrams 
1 ramko
2 rakom
3 okarm
4 morka
5 mokra
6 marko
7 makro
8 komar
9 karom
10 karmo
11 kamor
12 arkom
13 akrom

real    0m6.810s
user    0m6.535s
sys     0m0.325s

[toc] | [prev] | [next] | [standalone]

#28450

On Tuesday, April 5, 2016 at 2:32:10 PM UTC+2, M.M. wrote:
> On Tuesday, April 5, 2016 at 1:54:56 AM UTC+2, bartekltg wrote:
> > On 04.04.2016 17:35, Borneq wrote:
> > > 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
> > >> ?
> > 
> > Całkowicie wysatrczy.
> > 
> > > Tylko jak to sortować?,
> > 
> > funckją sort? ;-)
> > 
> > 
> > > sortowanie kubełkowe? czy to sortowanie nie
> > > stwarza problemów, gdy jakaś litera się powtarza,
> > 
> > Nie.
> > 
> > > Kubełków mogło by byc
> > > mało dla ASCII, ale trzeba by dużej liczby dla Unicodu
> > 
> > Hmm, ciekawostka, patrząc na tabelkę utf-8 traktując
> > wyrazy jak ciagi bajtów i sortując te bajty nie spowodujesz
> > niezamierzonej kolizji;-) żadne "ęąń" nie okaże się tym samym ciągiem
> > co "ółś"
> > 
> > 
> > Albo czegoś nie mówisz, albo przekombinowujesz:
> > 
> > 
> > #include <vector>
> > #include <string>
> > #include <iostream>
> > #include <algorithm>
> > 
> > 
> > 
> > using namespace std;
> > 
> > 
> > int main()
> > {
> > 
> >      vector <pair<string, string > > S;
> >      string str,strs;
> > 
> >      while ( cin>>str )
> >      {
> >          strs=str;
> >          sort(strs.begin(),strs.end());
> > 
> >          S.emplace_back( strs,str );
> >      }
> > 
> >      sort(S.begin(),S.end());
> > 
> >      for (auto it = S.begin(); it!=S.end();)
> >      {
> >          auto itend = next(it);
> >          while (itend!=S.end() && itend->first == it->first) ++itend;
> >          if (distance(it, itend)>1)
> >          {
> >              cout<<"-- "<<distance(it, itend)<<endl;
> >              while (it!=itend)
> >                  cout<<(it++)->second<<endl;
> > 
> >          }
> >          else it++;
> >      }
> > 
> >      return 0;
> > }
> > 
> > Dłużej piszę posta niż pisałem ten kod,
> > http://sjp.pl/slownik/growy/
> > 2.7 mln słow, 38MB,
> > time ./untitled <slowa.txt >bla.txt
> > real	0m5.638s
> > 
> > Nie jest poprawny dla unikodu, ale dzięki uwadze powyżej - działa ;-)
> > 
> > Rekordzista
> > -- 13
> > akrom
> > arkom
> > kamor
> > karmo
> > karom
> > komar
> > makro
> > marko
> > mokra
> > morka
> > okarm
> > rakom
> > ramko
> > 
> > 
> > pzdr
> > bartekltg
> 
> Na hash-table z QT działa z kompilacją 02 na procesorze i3 działa
> ciut wolniej:
> 
> 
> 
> int main(int argc, char *argv[])
> {
>     QTextStream in(stdin);
>     in.setCodec("UTF-8");
>     QString line;
>     QMultiHash<QString,QString> hash;
> 
>     while( ! ( line = in.readLine() ).isEmpty() ) {
>         QString sort = line;
>         qSort( sort.begin() , sort.end() );
>         hash.insert( sort , line );
>     }
> 
>     QStringList max;
>     QStringList keys = hash.uniqueKeys();
>     for( int i=0 ; i<keys.size() ; i++ ) {
>         if( max.size() < hash.values( keys[i] ).size() )
>             max = hash.values( keys[i] );
>     }
> 
>     for( int i=0 ; i<max.size() ; i++ )
>         printf("%d %s\n",i+1,qPrintable(max[i]));
>     fflush(stdout);
> 
>     return 0;
> }
> 
> 
> 
> 
> x@x:~/tmp/build-anagrams-Desktop-Release$ time cat ~/Pobrane/slowa.txt | ./anagrams 
> 1 ramko
> 2 rakom
> 3 okarm
> 4 morka
> 5 mokra
> 6 marko
> 7 makro
> 8 komar
> 9 karom
> 10 karmo
> 11 kamor
> 12 arkom
> 13 akrom
> 
> real    0m6.810s
> user    0m6.535s
> sys     0m0.325s

A samoróbka na hashach szybsza:


x@x:~/tmp/build-anagrams-Desktop-Release$ time cat ~/Pobrane/slowa.txt | ./anagrams
1 ramko
2 rakom
3 okarm
4 morka
5 mokra
6 marko
7 makro
8 komar
9 karom
10 karmo
11 kamor
12 arkom
13 akrom

real    0m2.962s
user    0m2.666s
sys     0m0.348s



#include <QString>
#include <QTextStream>

#define HASH_SIZE   (1024*1024*12)
#define STACK_SIZE  (1024*1024*3)
#define KEYS_SIZE   (1024)

struct Item {
    QString str;
    QString sort;
    Item    *next;
};

static int  count[HASH_SIZE];
static Item *hash[HASH_SIZE];
static Item stack[STACK_SIZE];
static int stack_size = 0;
static unsigned int keys[KEYS_SIZE];


static void initKeys() {
    for( int i=0 ; i<KEYS_SIZE*1 ; i++ )
        keys[i % KEYS_SIZE] = (keys[ i % KEYS_SIZE ] * 16) ^ qrand();
}


static unsigned int mkKey( const QString &str ) {
    unsigned int key = 0;
    for( int i=0 ; i<str.size() ; i++ )
        key ^= keys[ str[i].unicode() % KEYS_SIZE ];
    return key % HASH_SIZE;
}

static void insert( QString &str ) {
    unsigned int key = mkKey( str );
    stack[stack_size].str = str;
    qSort( str.begin() , str.end() );
    stack[stack_size].sort = str;
    while( hash[key] && hash[key]->sort != str )
        key = (key+1) % HASH_SIZE;
    if( hash[key] ) {
        stack[stack_size].next = hash[key];
    }
    hash[key] = stack + stack_size ++;
    count[key] ++ ;
}

int main( int argc, char *argv[] )
{
    qsrand(123);

    QTextStream in(stdin);
    in.setCodec("UTF-8");

    initKeys();

    QString line;

    while( ! ( line = in.readLine() ).isEmpty() ) {
        insert( line );
    }

    int max = 0;
    for( int i=1 ; i<HASH_SIZE ; i++ )
        if( count[max] < count[i] )
            max = i;
    Item *entry = hash[max];
    int nr=1;
    while( entry ) {
        printf("%d %s\n",nr++,qPrintable(entry->str));
        entry = entry->next;
    }


    return 0;
}

[toc] | [prev] | [next] | [standalone]

#28424

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

[toc] | [prev] | [next] | [standalone]

#28426

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

[toc] | [prev] | [next] | [standalone]

#28430

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

[toc] | [prev] | [next] | [standalone]

#28433

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

[toc] | [prev] | [standalone]

Back to top | Article view | pl.comp.programming

csiph-web