uu.seUppsala University Publications

CiteExport$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_upper_j_idt146",{id:"formSmash:upper:j_idt146",widgetVar:"widget_formSmash_upper_j_idt146",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:upper:exportLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt147_j_idt149",{id:"formSmash:upper:j_idt147:j_idt149",widgetVar:"widget_formSmash_upper_j_idt147_j_idt149",target:"formSmash:upper:j_idt147:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

Partial fillup and search time in LC triesPrimeFaces.cw("AccordionPanel","widget_formSmash_some",{id:"formSmash:some",widgetVar:"widget_formSmash_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_all",{id:"formSmash:all",widgetVar:"widget_formSmash_all",multiple:true});
function selectAll()
{
var panelSome = $(PrimeFaces.escapeClientId("formSmash:some"));
var panelAll = $(PrimeFaces.escapeClientId("formSmash:all"));
panelAll.toggle();
toggleList(panelSome.get(0).childNodes, panelAll);
toggleList(panelAll.get(0).childNodes, panelAll);
}
/*Toggling the list of authorPanel nodes according to the toggling of the closeable second panel */
function toggleList(childList, panel)
{
var panelWasOpen = (panel.get(0).style.display == 'none');
// console.log('panel was open ' + panelWasOpen);
for (var c = 0; c < childList.length; c++) {
if (childList[c].classList.contains('authorPanel')) {
clickNode(panelWasOpen, childList[c]);
}
}
}
/*nodes have styleClass ui-corner-top if they are expanded and ui-corner-all if they are collapsed */
function clickNode(collapse, child)
{
if (collapse && child.classList.contains('ui-corner-top')) {
// console.log('collapse');
child.click();
}
if (!collapse && child.classList.contains('ui-corner-all')) {
// console.log('expand');
child.click();
}
}
PrimeFaces.cw("AccordionPanel","widget_formSmash_responsibleOrgs",{id:"formSmash:responsibleOrgs",widgetVar:"widget_formSmash_responsibleOrgs",multiple:true}); 2007 (English)In: ACM Transactions on Algorithms, ISSN 1549-6325, E-ISSN 1549-6333, Vol. 3, no 4, 44:1-44:14 p.Article in journal (Refereed) Published
##### Abstract [en]

##### Place, publisher, year, edition, pages

2007. Vol. 3, no 4, 44:1-44:14 p.
##### National Category

Mathematics
##### Identifiers

URN: urn:nbn:se:uu:diva-12746DOI: 10.1145/1290672.1290681OAI: oai:DiVA.org:uu-12746DiVA: diva2:40515
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt434",{id:"formSmash:j_idt434",widgetVar:"widget_formSmash_j_idt434",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt440",{id:"formSmash:j_idt440",widgetVar:"widget_formSmash_j_idt440",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt446",{id:"formSmash:j_idt446",widgetVar:"widget_formSmash_j_idt446",multiple:true});
Available from: 2008-01-11 Created: 2008-01-11 Last updated: 2017-12-11Bibliographically approved

Andersson and Nilsson introduced in 1993 a *level-compressed trie* (for short, LC trie) in which a full subtree of a node is compressed to a single node of degree being the size of the subtree. Recent experimental results indicated a “dramatic improvement” when full subtrees are replaced by “partially filled subtrees.” In this article, we provide a theoretical justification of these experimental results, showing, among others, a rather moderate improvement in search time over the original LC tries. For such an analysis, we assume that *n* strings are generated independently by a binary memoryless source, with *p* denoting the probability of emitting a “1” (and *q* = 1 − *p*). We first prove that the so-called α-fillup level *F*_{n}(α) (i.e., the largest level in a trie with α fraction of nodes present at this level) is concentrated on two values with high probability: either *F*_{n}(α) = *k*_{n} or *F*_{n}(α) = *k*_{n} + 1, where *k*_{n} = log_{1/&sqrt;pq} *n* − |ln (*p/q*)|/2 ln^{3/2} (1&sqrt;*pq*) Φ^{−1} (α) &sqrt; ln *n* + *O*(1) is an integer and Φ(*x*) denotes the normal distribution function. This result directly yields the typical depth (search time) *D*_{n}(α) in the α-LC tries, namely, we show that with high probability *D*_{n}(α) ∼ *C*_{2} log log *n*, where *C*_{2} = 1/|log(1 − *h*/log(1/&sqrt;*pq*))| for *p* ≠ *q* and *h* = −*p*log *p*−*q*log *q* is the Shannon entropy rate. This should be compared with recently found typical depth in the original LC tries, which is *C*_{1}log log *n*, where *C*_{1} = 1/|log(1−*h*/log(1/min{*p*, 1−*p*}))|. In conclusion, we observe that α affects only the lower term of the α-fillup level *F*_{n}(α), and the search time in α-LC tries is of the same order as in the original LC tries.

doi
urn-nbn$(function(){PrimeFaces.cw("Tooltip","widget_formSmash_j_idt1144",{id:"formSmash:j_idt1144",widgetVar:"widget_formSmash_j_idt1144",showEffect:"fade",hideEffect:"fade",showDelay:500,hideDelay:300,target:"formSmash:altmetricDiv"});});

CiteExport$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_lower_j_idt1197",{id:"formSmash:lower:j_idt1197",widgetVar:"widget_formSmash_lower_j_idt1197",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:lower:exportLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_lower_j_idt1198_j_idt1200",{id:"formSmash:lower:j_idt1198:j_idt1200",widgetVar:"widget_formSmash_lower_j_idt1198_j_idt1200",target:"formSmash:lower:j_idt1198:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});