lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Dawid Weiss <dawid.we...@cs.put.poznan.pl>
Subject Re: Count of keys of an FST
Date Thu, 28 Jun 2012 13:36:38 GMT
Let me know if you need that snippet of code to count the keys; or try
it yourself -- should be good practice :)

Dawid

On Thu, Jun 28, 2012 at 3:32 PM, Jason Rutherglen
<jason.rutherglen@gmail.com> wrote:
> I looked at the sources and didn't see a key count.
>
> Thanks Dawid and Mike.
>
> On Thu, Jun 28, 2012 at 6:37 AM, Michael McCandless
> <lucene@mikemccandless.com> wrote:
>>
>> I believe node and arc count are stored, but not key count.  But check
>> the sources to be sure!
>>
>> Mike McCandless
>>
>> http://blog.mikemccandless.com
>>
>> On Wed, Jun 27, 2012 at 4:53 PM, Dawid Weiss
>> <dawid.weiss@cs.put.poznan.pl> wrote:
>> > 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.
>> >
>> > Dawid
>> >
>> > On Wed, Jun 27, 2012 at 10:50 PM, Jason Rutherglen
>> > <jason.rutherglen@gmail.com> 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
>> >> <dawid.weiss@cs.put.poznan.pl>
>> >> 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
>> >>> <jason.rutherglen@gmail.com> 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: dev-unsubscribe@lucene.apache.org
>> >>> For additional commands, e-mail: dev-help@lucene.apache.org
>> >>>
>> >>
>> >
>> > ---------------------------------------------------------------------
>> > To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
>> > For additional commands, e-mail: dev-help@lucene.apache.org
>> >
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
>> For additional commands, e-mail: dev-help@lucene.apache.org
>>
>

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org


Mime
View raw message