lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Dawid Weiss <>
Subject Re: Count of keys of an FST
Date Wed, 27 Jun 2012 20:53:29 GMT
If you need the count with constant time then yes, you should store it
separately. You could also make a transducer that would store it at
the root node as side-effect of values associated with keys, but it's
kind of ugly.

Please check the fst header though -- I'm not sure, maybe Mike wrote
it so that the node count/ keys count is in there.


On Wed, Jun 27, 2012 at 10:50 PM, Jason Rutherglen
<> wrote:
> Sounds like I should just count as the keys are added and store the count
> separately.
> On Wed, Jun 27, 2012 at 3:48 PM, Dawid Weiss <>
> wrote:
>> I don't think there is one that you could use out of the box... but
>> maybe I'm wrong and it's stored in the header somewhere (don't have
>> the source in front of me).
>> To calculate it by hand the worst case is that you'll need a recursive
>> traversal, which would mean O(number of stored states) with
>> intermediate count caches or O(number of keys) without any caches and
>> memory overhead (just recursive traversal).
>> Dawid
>> On Wed, Jun 27, 2012 at 10:36 PM, Jason Rutherglen
>> <> wrote:
>> > The FST class has a number of methods that return counts, which one
>> > returns
>> > the total number of keys that have been encoded into the FST?
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail:
>> For additional commands, e-mail:

To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message