nltk/nltk — Issue #86: Reimplement FreqDist
Author: alexrudnick
Created: 2012-01-17 06:25:45+00:00
State: open

Reimplement FreqDist to use collections.Counter, in NLTK 3.0.

http://docs.python.org/3.1/library/collections.html?highlight=counter#collections.Counter

Migrated from http://code.google.com/p/nltk/issues/detail?id=456

earlier comments

dchichkov said, at 2010-07-01T22:56:11.000Z:

A few comments:
1) Currently FreqDist is derived from dict(). While it is maybe convenient, it creates extra ambiguities in the interface.

2) Recalculating _N upon every inc() call is wasteful, especially in a way it is done now - via __setitem__ call.

3) For large data sets it is valuable to have a trimming method that deletes samples with frequencies/counts lower than a specified limit;

4) For large data sets it is valuable to have a trimming method that can be called during the data collection process and trims the FreqDist to a specified size (e.g. 100,000,000 samples). This trimming method should delete 'oldest' samples (FIFO basis) with the lowest frequencies. That can be implemented if an OrderedDict is used to store the samples (as an option during the construction).

5) Consider storing samples that occur only once (hapax legomena) in a separate bin (set). Potentially that could reduce memory usage and give overall performance boost. Something along these lines (the code is untested):
...........
self._d = dict()
self._s = set()
self._N = 0
self._Nr_cache = None
self._max_cache = None
self._item_cache = None
if samples:
self.update(samples)

def inc(self, sample, count=1):
"""
Increment this C{FreqDist}'s count for the given
sample.

@param sample: The sample whose count should be incremented.
@type sample: any
@param count: The amount to increment the sample's count by.
@type count: C{int}
@rtype: None
@raise NotImplementedError: If C{sample} is not a
supported sample type.
"""
if count == 0: return
self._N += count
if sample in self._d: self._d[sample] += count; return
if sample in self._s: self._d[sample] = count + 1; self._s.remove(sample); return
if count == 1: self._s.add(sample); return
self._d[sample] = count

def __getitem__(self, sample):
if sample in self._d: return self._d[sample]
if sample in self._s: return 1
return 0

def __setitem__(self, sample, value):
"""
Set this C{FreqDist}'s count for the given sample.

@param sample: The sample whose count should be incremented.
@type sample: any hashable object
@param count: The new value for the sample's count
@type count: C{int}
@rtype: None
@raise TypeError: If C{sample} is not a supported sample type.
"""

self._N += (value - self.__getitem__(sample)))
if sample in self._d and value <= 1: del delf._d[sample]
if sample in self._s and value != 1: self._s.remove(sample)
if value == 1: self._s.add(sample); return
if value > 1: self._d[sample] = value