Daha fazla sayıda yaprak için trie uzatılması

Deneme kullanarak bir sözlük yapmak zorundayım, alfabedeki harflerin sayısı 26'dan 120'ye artacak ve dolayısıyla yaprak düğümlerinin sayısı üssel olarak artacaktır. Arama, ekleme ve silme zamanımın katlanarak artmaması için hangi optimizasyonları kullanabilirim?Daha fazla sayıda yaprak için trie uzatılması

DÜZENLEME soru daha net yapma, detaylar Ben sayı tabanı ağaç gibi çok yönlü bir tray kullanarak ve ona bazı değişiklikler yapıyorum yetersizliğinden üzgün. Benim sorum, eğer kelime büyüklüğünün 26'dan 120'ye kadar (kesinlikle) artacağını bilirsem, ağacın derinliğini arttıracağım. Anahtarın 64 bitten daha fazla arttırılmasıyla derinlikteki artışı azaltmak mümkün mü (kayıt en fazla 64 bit altın yapabilir)?

kaynak

2016-03-24 Anonymous

neden üssel olarak artacak? –

Ne sorduğun belli değil. Alfabeniz genişliyor mu, yoksa kelimelerin uzunluğu uzuyor mu? Somut bir örnek yardımcı olabilir. –

Başlangıçta, trie, 32 karakterlik uzunluğa sahip kelimeleri işlemek üzere tasarlanmıştı, şimdi de trie, 120 karakter uzunluğundaki kelimeleri işlemek zorunda. Kelimelerin uzunluğu büyüyor. –

Anahtarların ikili gösterimini temel alarak yol sıkıştırmasıyla ikili denemelerin (Patricia denemeleri) kullanılması genellikle daha iyidir. Bu sayede mümkün olan en küçük alfabenin avantajlarını elde edersiniz ve anahtar başına sadece 2 düğüm (bir yaprak ve bir iç) vardır.

kaynak

2016-03-25 04:37:21

Bir radix ağacının uygulanma biçiminde değişiklikler yapıyorum (M = 2^k olan çok yollu bir tray). Burada k, arama için kullanılan bitlerin sayısıdır. Eğer k = 6 ise 64 bitlik CPU Mimarisinin kayıtlarının büyüklüğüne uyuyor, ancak k'yi 10'a çıkardığımı varsayalım, bunu nasıl uygulayabilirim? Not: Zamanı azaltmak için derinlik yerine M artırmak istiyorum. –

Bazı optimizasyonlar olsa da, ancak arama, ekleme ve silme süreleri katlanarak artmayacaktır. Alfabe kümenizi artırmanız, yalnızca her bir düğüm düğmenizin artık daha büyük olacağı anlamına gelir. Her bir kelimenin yolu, kelimedeki harflere eşit olan aynı uzunluğa sahip olacaktır.

kaynak

2016-03-25 04:42:59 displayName

Daha fazla sayıda yaprak için trie uzatılması

cevap

İlgili konular