python: pencarian kata kamus cepat dengan wildcard*

Mengingat sebuah teks, yang dipecah menjadi daftar kata, saya ingin mencari setiap kata dalam kamus kata, yang juga dibaca dari file teks dan split('\n').

Daripada memeriksa apakah setiap kata terdapat dalam kamus (yang sangat lambat) saya perlu memilih daftar elemen berdasarkan wildcard* ('*' ada di akhir yaitu tidak diperlukan solusi permuterm). Misalnya, solusinya harus memilih semua elemen kamus yang dimulai dengan 'dep', tanpa melintasi seluruh daftar kamus.

Kinerja sangat penting dalam hal ini. Saya pikir dari Btree...tapi

  1. Paket dan tipe data apa yang terbaik untuk implementasi cepat dengan Python.
  2. Harap berikan contoh kode

python dictionary lookup tree
person Lorenz Lo Sauer    schedule 03.10.2011    source sumber
comment
Sepertinya Anda memerlukan paket trie   -  person Voo    schedule 03.10.2011
comment
Masalah wildcard pasti akan selalu lebih lambat. Dikte berfungsi dengan hash (waktu akses yang konstan).   -  person JBernardo    schedule 03.10.2011
comment
@JBernardo: tidak, itu berarti elemen harus dimulai dengan apa pun yang ada sebelum 'bintang'   -  person Lorenz Lo Sauer    schedule 03.10.2011
comment
Itu sebabnya Anda akan kehilangan pencarian waktu yang konstan. yaitu Ini akan menjadi lebih lambat.   -  person JBernardo    schedule 03.10.2011

Jawaban (2)


arrow_upward
2
arrow_downward

Gunakan dawg, yang lebih efisien dibandingkan Trie dalam hal pemborosan ruang. Ada beberapa implementasi python, tapi sebagai permulaan, lihat di sini.

person hymloth    schedule 03.10.2011
comment
Dari situs web: ...Jika Anda tidak peduli dengan memori atau kecepatan[sic!], simpan saja kata-kata Anda... Apakah lebih cepat? - person Lorenz Lo Sauer; 03.10.2011
comment
Dawgnya pasti lebih cepat. Kutipan dari situs web ini ironis. cukup simpan kata-kata Anda di database SQL, atau jalankan 100 mesin di cloud. Saya tidak keberatan. Lebih banyak kekuatan untuk Anda! - person hymloth; 03.10.2011

arrow_upward
2
arrow_downward

Anda ingin mencoba. Gunakan paket PyTrie.

person Petr Viktorin    schedule 03.10.2011