Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Patricia trie vs binary search.
173 views
Skip to first unread message
markspace
May 24, 2012, 7:07:14 PM5/24/12
to
For some reason I was thinking about sub-string searches today. I
looked up Patricia tries (a kind of radix tree) to see if they would
help. While interesting, the radix tree seems to have a lot of overhead
for large numbers of entries.
The radix tree uses a bucket at each level to hold all children (and
there could be quite a lot of children). Each child if present requires
a pointer (an object in Java) to hold it. For the example given, this
could be as much as one object per character in each string, plus the
bucket to hold it and its siblings. If the number strings is very
large, this could really result in an explosion of memory usage.
<http://en.wikipedia.org/wiki/Radix_tree>
So is there a better way for large data sets?
For the example give, it appears to be a kind of incremental search.
Those, first we find the "r" which is common to all the words in the
example. Then if we're looking for, say, "romane" we'd find that the
"om" is common to all words that match. Then we find that "an" matches
both "romane" and "romanus". Finally we find the "e" which tells us
"romane" exist in the tree.
So I implemented a simple "incremental binary search". Given a string,
the search tells you if there's any elements that begin with the
parameter string. It also remembers the previous match, so that the
next search picks up from that location. "ro" could be matched next
along with "rom". If the search ever returns a non-match condition, you
know you've hit the maximum extent. There are no further matches,
regardless how many additional characters you append.
This seems useful for "short-circuiting" long string matches, allowing
you to pick out dictionary matches without inuring average n^2 time.
My question is: does this really buy me anything? Or did I just
duplicate some other well known algorithms that works just as well or
better?
/*
* Copyright 2012 Brenden Towey. All rights reserved.
*/
package com.techdarwinia.trie;
import java.io.FileReader;
import java.io.Reader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
/**
*
* @author Brenden Towey
*/
public class IncrementalStringSearch
{
private int low;
private int high;
private String[] array;
public IncrementalStringSearch( String[] array )
{
this.array = array;
high = array.length - 1;
}
public boolean find( String findString )
{
if( low > high ) return false;
for( ;; ) {
int index = ( low + high ) / 2;
String foundSub = array[index];
if( array[index].length() > findString.length() )
foundSub = array[index].substring( 0, findString.length() );
else
foundSub = array[index];
if( foundSub.equals( findString ) )
return true;
if( foundSub.compareTo( findString ) > 0 ) {
high = index - 1;
if( high < low ) return false;
} else {
low = index + 1;
if( low > high ) return false;
}
}
}
public static void main( String[] args ) throws Exception
{
ArrayList<String> passwords = new ArrayList<>();
Reader ins = new FileReader( "test/com/techdarwinia/trie/bpw.txt" );
Scanner scanner = new Scanner( ins );
scanner.useDelimiter( ",?\\s+" );
while( scanner.hasNext() ) {
passwords.add( scanner.next() );
}
ins.close();
Collections.sort( passwords );
String test = "passxword ";
for( int i = 0; i < test.length(); i++ ) {
IncrementalStringSearch inc = new IncrementalStringSearch(
passwords.toArray( new String[0] ) );
for( int j = i + 1; j <= test.length(); j++ ) {
String string = test.substring( i, j );
if( !inc.find( string ) ){
if( j > i+1 && passwords.contains( test.substring( i,
j-1 ) ) ) {
System.out.println( "Found: "+test.substring( i, j-1 ) );
}
break;
}
}
}
}
}
looked up Patricia tries (a kind of radix tree) to see if they would
help. While interesting, the radix tree seems to have a lot of overhead
for large numbers of entries.
The radix tree uses a bucket at each level to hold all children (and
there could be quite a lot of children). Each child if present requires
a pointer (an object in Java) to hold it. For the example given, this
could be as much as one object per character in each string, plus the
bucket to hold it and its siblings. If the number strings is very
large, this could really result in an explosion of memory usage.
<http://en.wikipedia.org/wiki/Radix_tree>
So is there a better way for large data sets?
For the example give, it appears to be a kind of incremental search.
Those, first we find the "r" which is common to all the words in the
example. Then if we're looking for, say, "romane" we'd find that the
"om" is common to all words that match. Then we find that "an" matches
both "romane" and "romanus". Finally we find the "e" which tells us
"romane" exist in the tree.
So I implemented a simple "incremental binary search". Given a string,
the search tells you if there's any elements that begin with the
parameter string. It also remembers the previous match, so that the
next search picks up from that location. "ro" could be matched next
along with "rom". If the search ever returns a non-match condition, you
know you've hit the maximum extent. There are no further matches,
regardless how many additional characters you append.
This seems useful for "short-circuiting" long string matches, allowing
you to pick out dictionary matches without inuring average n^2 time.
My question is: does this really buy me anything? Or did I just
duplicate some other well known algorithms that works just as well or
better?
/*
* Copyright 2012 Brenden Towey. All rights reserved.
*/
package com.techdarwinia.trie;
import java.io.FileReader;
import java.io.Reader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
/**
*
* @author Brenden Towey
*/
public class IncrementalStringSearch
{
private int low;
private int high;
private String[] array;
public IncrementalStringSearch( String[] array )
{
this.array = array;
high = array.length - 1;
}
public boolean find( String findString )
{
if( low > high ) return false;
for( ;; ) {
int index = ( low + high ) / 2;
String foundSub = array[index];
if( array[index].length() > findString.length() )
foundSub = array[index].substring( 0, findString.length() );
else
foundSub = array[index];
if( foundSub.equals( findString ) )
return true;
if( foundSub.compareTo( findString ) > 0 ) {
high = index - 1;
if( high < low ) return false;
} else {
low = index + 1;
if( low > high ) return false;
}
}
}
public static void main( String[] args ) throws Exception
{
ArrayList<String> passwords = new ArrayList<>();
Reader ins = new FileReader( "test/com/techdarwinia/trie/bpw.txt" );
Scanner scanner = new Scanner( ins );
scanner.useDelimiter( ",?\\s+" );
while( scanner.hasNext() ) {
passwords.add( scanner.next() );
}
ins.close();
Collections.sort( passwords );
String test = "passxword ";
for( int i = 0; i < test.length(); i++ ) {
IncrementalStringSearch inc = new IncrementalStringSearch(
passwords.toArray( new String[0] ) );
for( int j = i + 1; j <= test.length(); j++ ) {
String string = test.substring( i, j );
if( !inc.find( string ) ){
if( j > i+1 && passwords.contains( test.substring( i,
j-1 ) ) ) {
System.out.println( "Found: "+test.substring( i, j-1 ) );
}
break;
}
}
}
}
}
glen herrmannsfeldt
May 24, 2012, 7:39:23 PM5/24/12
to
markspace <-@.> wrote:
> For some reason I was thinking about sub-string searches today. I
> looked up Patricia tries (a kind of radix tree) to see if they would
> help. While interesting, the radix tree seems to have a lot of overhead
> for large numbers of entries.
I am not so sure which substring problem you are interested in,
> For some reason I was thinking about sub-string searches today. I
> looked up Patricia tries (a kind of radix tree) to see if they would
> help. While interesting, the radix tree seems to have a lot of overhead
> for large numbers of entries.
but you might look at the Aho-Korasick algorithm.
If you want to allow for insertions and/or deletions, look
at dynamic programming.
-- glen
markspace
May 24, 2012, 8:56:14 PM5/24/12
to
was referring to was picking words out of a longer, undelimited string.
The example I posted looked for bad passwords within a larger password.
"passxword" contains at least two bad passwords, pass and word,
according to the dictionary file I download from here (that's the
bpw.txt file in the sample code):
<http://www.godlikeproductions.com/badpasswords.php>
The code I posted find pass, ass, word, and or in the string
"passxword", which are all bad passwords according to that link above.
(I deliberately avoid reporting single letters as bad).
Practically speaking, hashing appears to be just as fast for a lookup,
but hashing doesn't tell you when to stop, so it's always N^2 for this
sort of problem. My algorithm should average less, hopefully much less
if you have very long input strings.
I really don't know what set me off looking at this; it's just a little
random experiment I suppose.
Lew
May 25, 2012, 12:41:25 PM5/25/12
to
markspace wrote:
> Thanks for those pointers (pun not intended). The "sub-string search"
> was referring to was picking words out of a longer, undelimited string.
>
> The example I posted looked for bad passwords within a larger password.
>
> "passxword" contains at least two bad passwords, pass and word,
> according to the dictionary file I download from here (that's the
> bpw.txt file in the sample code):
>
> <http://www.godlikeproductions.com/badpasswords.php>
>
> The code I posted find pass, ass, word, and or in the string
> "passxword", which are all bad passwords according to that link above.
> (I deliberately avoid reporting single letters as bad).
I wonder about eliminating two-letter combinations. How much entropy does that add (or subtract) from passwords?
> Thanks for those pointers (pun not intended). The "sub-string search"
> was referring to was picking words out of a longer, undelimited string.
>
> The example I posted looked for bad passwords within a larger password.
>
> "passxword" contains at least two bad passwords, pass and word,
> according to the dictionary file I download from here (that's the
> bpw.txt file in the sample code):
>
> <http://www.godlikeproductions.com/badpasswords.php>
>
> The code I posted find pass, ass, word, and or in the string
> "passxword", which are all bad passwords according to that link above.
> (I deliberately avoid reporting single letters as bad).
It's practicable and arguably more reliable to use passphrases comprising
all natural words whose entropy exceeds that of a fairly long Mxyzptlk®
key. (Note: "Mxyzptlk" may well pass all your password checks, yet is highly
guessable. Equally flawed are other stringlets that pass naive checks,
like "XB-17", "UB40" and others.) See
http://world.std.com/~reinhold/diceware.html
for how to create high-entropy, highly memorable passphrases.
> Practically speaking, hashing appears to be just as fast for a lookup,
> but hashing doesn't tell you when to stop, so it's always N^2 for this
> sort of problem. My algorithm should average less, hopefully much less
> if you have very long input strings.
>
> I really don't know what set me off looking at this; it's just a little
> random experiment I suppose.
a fairly well-studied problem. I don't off the top of my head have better
answers, but your approach to experiment is viable.
You could instrument (profile) your code over different algorithms and
input dataset profiles (that is, relative proportion of long, medium-length
and short strings, relative proportion of "bad" substrings in the mix, and
other factors that affect the "shape" of the data your algorithms process).
Algorithm analysis should give you the big O, but not the constant factors
or where they break for lower /n/.
A lot of algorithm analysis critically depends on what constitutes "average"
datasets.
--
Lew
markspace
May 25, 2012, 3:17:09 PM5/25/12
to
On 5/25/2012 9:41 AM, Lew wrote:
>
> I wonder about eliminating two-letter combinations. How much entropy
> does that add (or subtract) from passwords?
I was thinking the same thing. Also searching for the longest possible
>
> I wonder about eliminating two-letter combinations. How much entropy
> does that add (or subtract) from passwords?
word, and not bactracking, might be sufficient. Once you find "word",
why go back and scan for two or three letter combinations?
>
> It's practicable and arguably more reliable to use passphrases
> comprising all natural words whose entropy exceeds that of a fairly
> long Mxyzptlk® key. (Note: "Mxyzptlk" may well pass all your password
> checks, yet is highly guessable. Equally flawed are other stringlets
users may defeat your requirement by just repeating a shorter bad
password. "birdbirdbirdbird" is a pretty guessable 16 letter password,
and "bird" appears in the bad password list. However,
"birdaliceferretsalut" is a pretty decent password, even though each of
its four component words appears in the bad password list. So if you
can spot the individual component words and make sure they don't repeat,
you've improved entropy a bit.
> that pass naive checks, like "XB-17", "UB40" and others.) See
> http://world.std.com/~reinhold/diceware.html for how to create
> high-entropy, highly memorable passphrases.
least 5 to 7 different characters. So even though "UB40UB40UB40UB40" is
16 characters and no sub-words appear on the bad password list, it only
uses 4 different characters, which we might not want to allow.
> Your main question of space- and time-efficient substring matching
> is a fairly well-studied problem. I don't off the top of my head have
> better answers, but your approach to experiment is viable.
implement each algorithm such that it was optimal, and I don't always
have the skill or time to do that. "Many eyes" on a problem is often
the more efficient solution. (This is also know as "research" and "not
re-inventing the wheel".) Though certainly it wouldn't hurt to make the
attempt.
Glen's answer above was very helpful. Wikipedia has cross-referenced
their string-matching algorithms so that finding one leads to all the
others.
<http://en.wikipedia.org/wiki/Category:String_matching_algorithms>
This gives me something to chew on, at least.
Daniel Pitts
May 26, 2012, 8:30:17 PM5/26/12
to
On 5/24/12 4:07 PM, markspace wrote:
> For some reason I was thinking about sub-string searches today. I looked
> up Patricia tries (a kind of radix tree) to see if they would help.
> While interesting, the radix tree seems to have a lot of overhead for
> large numbers of entries.
>
> The radix tree uses a bucket at each level to hold all children (and
> there could be quite a lot of children). Each child if present requires
> a pointer (an object in Java) to hold it. For the example given, this
> could be as much as one object per character in each string, plus the
> bucket to hold it and its siblings. If the number strings is very large,
> this could really result in an explosion of memory usage.
I tend to use a Deterministic Finite State Automata for this. You can
> For some reason I was thinking about sub-string searches today. I looked
> up Patricia tries (a kind of radix tree) to see if they would help.
> While interesting, the radix tree seems to have a lot of overhead for
> large numbers of entries.
>
> The radix tree uses a bucket at each level to hold all children (and
> there could be quite a lot of children). Each child if present requires
> a pointer (an object in Java) to hold it. For the example given, this
> could be as much as one object per character in each string, plus the
> bucket to hold it and its siblings. If the number strings is very large,
> this could really result in an explosion of memory usage.
load the entire English dictionary fairly easily with that scheme. Yes,
you use a bit of memory, but unless you're doing this on an embedded
device, its probably not enough memory to be concerned about.
Most of what I know about "searching" and "parsing", I've learned from
"Parsing Techniques - A Practical Guide"
<http://dickgrune.com/Books/PTAPG_1st_Edition/>. Free PDF or PS
downloads on that page.
Very worth a read. I'm sure parsing theory has been much extended since
this book was written, however it is definitely a good introduction to
the concepts in the space.
HTH,
Daniel.
markspace
May 26, 2012, 9:17:30 PM5/26/12
to
That looks very interesting. Thanks! I'll have to check it out.
Gene Wirchenko
May 27, 2012, 9:44:11 PM5/27/12
to
On Sat, 26 May 2012 17:30:17 -0700, Daniel Pitts
<newsgrou...@virtualinfinity.net> wrote:
[snip]
>I tend to use a Deterministic Finite State Automata for this. You can
>load the entire English dictionary fairly easily with that scheme. Yes,
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
[snip]
Sincerely,
Gene Wirchenko
<newsgrou...@virtualinfinity.net> wrote:
[snip]
>I tend to use a Deterministic Finite State Automata for this. You can
>load the entire English dictionary fairly easily with that scheme. Yes,
>you use a bit of memory, but unless you're doing this on an embedded
>device, its probably not enough memory to be concerned about.
Including all affixes?
>device, its probably not enough memory to be concerned about.
[snip]
Sincerely,
Gene Wirchenko
Daniel Pitts
May 28, 2012, 1:00:14 AM5/28/12
to
talking a few hundred thousand entries, at least with the Moby
word-lists as a base:
cat compound-words.txt often-mispelled.txt english-most-frequent.txt
male-names.txt female-names.txt common-names.txt common-dictionary.txt
official-scrabble-* | sort | uniq | wc -lc
388997 4801599
That's just over 4MB of strings, if stored as naively as possible.
Certainly no problem for a modern day computer. It can actually be quite
compressed when converted it to a DFSA, assuming reasonably optimized
implementations.
>
> [snip]
>
> Sincerely,
>
> Gene Wirchenko
markspace
May 28, 2012, 11:20:25 AM5/28/12
to
On 5/27/2012 10:00 PM, Daniel Pitts wrote:
> the Moby
> word-lists
Moby word lists are neat, thanks for pointing that out.
> the Moby
> word-lists
Moby word lists are neat, thanks for pointing that out.
Gene Wirchenko
May 28, 2012, 12:20:34 PM5/28/12
to
On Sun, 27 May 2012 22:00:14 -0700, Daniel Pitts
that very questionable:
self:
*ish
*ishly
un*ish
un*ishly
*less
*lessly
un*less
un*lessly
position:
*s
*ed
*al
*ally
re*
re*s
re*ed
*less
mis*
*er
*ers
friend
*s
*ly
*liness
be*
be*ing
be*ed
be*er
be*ers
These are not particularly extreme examples.
[snip]
Sincerely,
Gene Wirchenko
<newsgrou...@virtualinfinity.net> wrote:
>On 5/27/12 6:44 PM, Gene Wirchenko wrote:
>> On Sat, 26 May 2012 17:30:17 -0700, Daniel Pitts
>> <newsgrou...@virtualinfinity.net> wrote:
>>
>> [snip]
>>
>>> I tend to use a Deterministic Finite State Automata for this. You can
>>> load the entire English dictionary fairly easily with that scheme. Yes,
>> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>>> you use a bit of memory, but unless you're doing this on an embedded
>>> device, its probably not enough memory to be concerned about.
>>
>> Including all affixes?
>I suppose it depends on the particular dictionary, but we're only
>talking a few hundred thousand entries, at least with the Moby
>word-lists as a base:
Considering how many affixes can be applied to some words, I find
>On 5/27/12 6:44 PM, Gene Wirchenko wrote:
>> On Sat, 26 May 2012 17:30:17 -0700, Daniel Pitts
>> <newsgrou...@virtualinfinity.net> wrote:
>>
>> [snip]
>>
>>> I tend to use a Deterministic Finite State Automata for this. You can
>>> load the entire English dictionary fairly easily with that scheme. Yes,
>> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>>> you use a bit of memory, but unless you're doing this on an embedded
>>> device, its probably not enough memory to be concerned about.
>>
>> Including all affixes?
>I suppose it depends on the particular dictionary, but we're only
>talking a few hundred thousand entries, at least with the Moby
>word-lists as a base:
that very questionable:
self:
*ish
*ishly
un*ish
un*ishly
*less
*lessly
un*less
un*lessly
position:
*s
*ed
*al
*ally
re*
re*s
re*ed
*less
mis*
*er
*ers
friend
*s
*ly
*liness
be*
be*ing
be*ed
be*er
be*ers
These are not particularly extreme examples.
[snip]
Sincerely,
Gene Wirchenko
markspace
May 28, 2012, 5:38:49 PM5/28/12
to
to other corpus and word lists:
http://corpus.byu.edu/
Lew
May 29, 2012, 12:54:39 AM5/29/12
to
Not all words can be legitimately affixed. Many can be affixed by algorithm,
or by bitmaps as to which affixes apply, so you only store the root, the
bitmap and perhaps one more form.
I don't know how much memory expansion you think your factors will cause, as
you only hand wave and say there will be some and act like it's a problem, but
let's say it doubles the size of the dictionary. By Daniel's experiment
upthread, that would bring it to around 8 MiB, let's round and say 10MiB.
Being text and all, that should compress to about 3 MiB or less.
Now I am interested to hear what sort of trouble you assert that 3 MiB or so
of storage will cause.
--
Lew
Honi soit qui mal y pense.
http://upload.wikimedia.org/wikipedia/commons/c/cf/Friz.jpg
Jeff Higgins
May 29, 2012, 9:24:16 AM5/29/12
to
On 05/24/2012 07:07 PM, markspace wrote:
> For some reason I was thinking about sub-string searches today. I
> looked up Patricia tries (a kind of radix tree) to see if they would
> help. While interesting, the radix tree seems to have a lot of overhead
> for large numbers of entries.
>
> The radix tree uses a bucket at each level to hold all children (and
> there could be quite a lot of children). Each child if present requires
> a pointer (an object in Java) to hold it. For the example given, this
> could be as much as one object per character in each string, plus the
> bucket to hold it and its siblings. If the number strings is very large,
> this could really result in an explosion of memory usage.
>
> <http://en.wikipedia.org/wiki/Radix_tree>
>
> So is there a better way for large data sets?
>
Different. Better?
> For some reason I was thinking about sub-string searches today. I
> looked up Patricia tries (a kind of radix tree) to see if they would
> help. While interesting, the radix tree seems to have a lot of overhead
> for large numbers of entries.
>
> The radix tree uses a bucket at each level to hold all children (and
> there could be quite a lot of children). Each child if present requires
> a pointer (an object in Java) to hold it. For the example given, this
> could be as much as one object per character in each string, plus the
> bucket to hold it and its siblings. If the number strings is very large,
> this could really result in an explosion of memory usage.
>
> <http://en.wikipedia.org/wiki/Radix_tree>
>
> So is there a better way for large data sets?
>
<http://www.pathcom.com/~vadco/cwg.html>
Gene Wirchenko
May 29, 2012, 12:14:28 PM5/29/12
to
On Mon, 28 May 2012 21:54:39 -0700, Lew <no...@lewscanon.com> wrote:
>On 05/28/2012 09:20 AM, Gene Wirchenko wrote:
>> On Sun, 27 May 2012 22:00:14 -0700, Daniel Pitts
>> <newsgrou...@virtualinfinity.net> wrote:
>>
>>> On 5/27/12 6:44 PM, Gene Wirchenko wrote:
[snip]
>On 05/28/2012 09:20 AM, Gene Wirchenko wrote:
>> On Sun, 27 May 2012 22:00:14 -0700, Daniel Pitts
>> <newsgrou...@virtualinfinity.net> wrote:
>>
>>> On 5/27/12 6:44 PM, Gene Wirchenko wrote:
>> These are not particularly extreme examples.
>
>It's not a question of how extreme the examples are but how many there are.
not that unusual. There are a lot of them.
>Not all words can be legitimately affixed. Many can be affixed by algorithm,
>or by bitmaps as to which affixes apply, so you only store the root, the
>bitmap and perhaps one more form.
into aggregate affixes. e.g. -less + -ness -> -lessness.
>I don't know how much memory expansion you think your factors will cause, as
>you only hand wave and say there will be some and act like it's a problem, but
>let's say it doubles the size of the dictionary. By Daniel's experiment
English language actually is in his dataset.
>upthread, that would bring it to around 8 MiB, let's round and say 10MiB.
>Being text and all, that should compress to about 3 MiB or less.
>
>Now I am interested to hear what sort of trouble you assert that 3 MiB or so
>of storage will cause.
http://oxforddictionaries.com/words/how-many-words-are-there-in-the-english-language
is short but interesting reading. Its final paragraph: "This suggests
that there are, at the very least, a quarter of a million distinct
English words, excluding inflections, and words from technical and
regional vocabulary not covered by the OED, or words not yet added to
the published dictionary, of which perhaps 20 per cent are no longer
in current use. If distinct senses were counted, the total would
probably approach three quarters of a million."
Now, add on what they exclude. Is one million words out of line?
Itis one thing to have some of a language encoded. It is quite
another to try to handle everything. Exceptional cases tend to be
more difficult to handle.
Sincerely,
Gene Wirchenko
Daniel Pitts
May 29, 2012, 12:16:50 PM5/29/12
to
inflections of the words that it is used for.
For example "ishly" and "ness" suffixes:
> grep "ishly\b" * | wc -l
323
Which includes:
wordishly
womanishly
wolfishly
wishly
winterishly
wildishly
whorishly
whoreishly
Most of these entries aren't even in Thunderbirds spell-check dictionary.
> grep "ness\b" * | wc -l
11762
Includes entries such as:
woodlessness
wonderfulness
unmysteriousness
unexperiencedness
undeceptiveness
nonvolatileness
Again, most of these aren't spell-check.
My numbers are accurate, but thanks for questioning them, so I could
further explore and see for myself.
Daniel Pitts
May 29, 2012, 12:55:02 PM5/29/12
to
On 5/29/12 9:14 AM, Gene Wirchenko wrote:
> On Mon, 28 May 2012 21:54:39 -0700, Lew<no...@lewscanon.com> wrote:
>
>> On 05/28/2012 09:20 AM, Gene Wirchenko wrote:
>>> On Sun, 27 May 2012 22:00:14 -0700, Daniel Pitts
>>> <newsgrou...@virtualinfinity.net> wrote:
>>>
>>>> On 5/27/12 6:44 PM, Gene Wirchenko wrote:
>
> [snip]
>
>>> These are not particularly extreme examples.
>>
>> It's not a question of how extreme the examples are but how many there are.
>
> I mentioned extremity just to point out that such base words are
> not that unusual. There are a lot of them.
>
>> Not all words can be legitimately affixed. Many can be affixed by algorithm,
>> or by bitmaps as to which affixes apply, so you only store the root, the
>> bitmap and perhaps one more form.
>
> There are multiple affixes. I suppose they could be combined
> into aggregate affixes. e.g. -less + -ness -> -lessness.
>
>> I don't know how much memory expansion you think your factors will cause, as
>> you only hand wave and say there will be some and act like it's a problem, but
>> let's say it doubles the size of the dictionary. By Daniel's experiment
>
> Let's not make up data. I would like to know how much of the
> English language actually is in his dataset.
Agreed, let's not make up data. Using the Moby word-list as a guide, it
> On Mon, 28 May 2012 21:54:39 -0700, Lew<no...@lewscanon.com> wrote:
>
>> On 05/28/2012 09:20 AM, Gene Wirchenko wrote:
>>> On Sun, 27 May 2012 22:00:14 -0700, Daniel Pitts
>>> <newsgrou...@virtualinfinity.net> wrote:
>>>
>>>> On 5/27/12 6:44 PM, Gene Wirchenko wrote:
>
> [snip]
>
>>> These are not particularly extreme examples.
>>
>> It's not a question of how extreme the examples are but how many there are.
>
> I mentioned extremity just to point out that such base words are
> not that unusual. There are a lot of them.
>
>> Not all words can be legitimately affixed. Many can be affixed by algorithm,
>> or by bitmaps as to which affixes apply, so you only store the root, the
>> bitmap and perhaps one more form.
>
> There are multiple affixes. I suppose they could be combined
> into aggregate affixes. e.g. -less + -ness -> -lessness.
>
>> I don't know how much memory expansion you think your factors will cause, as
>> you only hand wave and say there will be some and act like it's a problem, but
>> let's say it doubles the size of the dictionary. By Daniel's experiment
>
> Let's not make up data. I would like to know how much of the
> English language actually is in his dataset.
includes a significant number of those particular suffixes and prefixes
you've mentioned. Granted, its not a complete word-list, but then again
nothing is. It is "complete enough" for most purposes.
>
>> upthread, that would bring it to around 8 MiB, let's round and say 10MiB.
>> Being text and all, that should compress to about 3 MiB or less.
>>
>> Now I am interested to hear what sort of trouble you assert that 3 MiB or so
>> of storage will cause.
>
> Assuming your facts and then calling me on what you made up?
>
> http://oxforddictionaries.com/words/how-many-words-are-there-in-the-english-language
> is short but interesting reading. Its final paragraph: "This suggests
> that there are, at the very least, a quarter of a million distinct
> English words, excluding inflections, and words from technical and
> regional vocabulary not covered by the OED, or words not yet added to
> the published dictionary, of which perhaps 20 per cent are no longer
> in current use. If distinct senses were counted, the total would
> probably approach three quarters of a million."
>
> Now, add on what they exclude. Is one million words out of line?
> Itis one thing to have some of a language encoded. It is quite
> another to try to handle everything. Exceptional cases tend to be
> more difficult to handle.
A modern desktop has more than enough memory to easily handle a quarter
*billion* words, which is a 100 times greater than your guessed upper limit.
And that's *without* compression.
Jeff Higgins
May 29, 2012, 1:37:53 PM5/29/12
to
On 05/29/2012 12:16 PM, Daniel Pitts wrote:
>
> Most of these entries aren't even in Thunderbirds spell-check dictionary.
>
How many seven letter words can I construct from the twenty-six letters
>
> Most of these entries aren't even in Thunderbirds spell-check dictionary.
>
A through Z? How many of these words are defined English words? What
are/are not the common affixes in this set of English words?
Daniel Pitts
May 29, 2012, 1:49:44 PM5/29/12
to
analyses? It is a very simple grep for the first question.
egrep "\b[a-zA-Z]{7}\b" *.txt
Jeff Higgins
May 29, 2012, 1:58:33 PM5/29/12
to
On 05/29/2012 01:49 PM, Daniel Pitts wrote:
> On 5/29/12 10:37 AM, Jeff Higgins wrote:
>> On 05/29/2012 12:16 PM, Daniel Pitts wrote:
>>>
>>> Most of these entries aren't even in Thunderbirds spell-check
>>> dictionary.
>>>
>> How many seven letter words can I construct from the twenty-six letters
>> A through Z? How many of these words are defined English words? What
>> are/are not the common affixes in this set of English words?
>
> How about you download the Moby word list yourself and do these
> analyses?
I was asking you.
> On 5/29/12 10:37 AM, Jeff Higgins wrote:
>> On 05/29/2012 12:16 PM, Daniel Pitts wrote:
>>>
>>> Most of these entries aren't even in Thunderbirds spell-check
>>> dictionary.
>>>
>> How many seven letter words can I construct from the twenty-six letters
>> A through Z? How many of these words are defined English words? What
>> are/are not the common affixes in this set of English words?
>
> How about you download the Moby word list yourself and do these
> analyses?
It is a very simple grep for the first question.
> egrep "\b[a-zA-Z]{7}\b" *.txt
Nope.
> egrep "\b[a-zA-Z]{7}\b" *.txt
Gene Wirchenko
May 29, 2012, 2:17:01 PM5/29/12
to
On Tue, 29 May 2012 09:55:02 -0700, Daniel Pitts
<newsgrou...@virtualinfinity.net> wrote:
[snip]
>Are you arguing that a modern system can't handle that number of words?
No. I simply stating that the real size of the problem is much
bigger.
>A modern desktop has more than enough memory to easily handle a quarter
>*billion* words, which is a 100 times greater than your guessed upper limit.
>
>And that's *without* compression.
Sure. If that is all that it does. My main (and older) desktop
box has 1.5 GB. I have trouble with not enough memory at times.
Adding another app might break its back.
Sincerely,
Gene Wirchenko
<newsgrou...@virtualinfinity.net> wrote:
[snip]
>Are you arguing that a modern system can't handle that number of words?
bigger.
>A modern desktop has more than enough memory to easily handle a quarter
>*billion* words, which is a 100 times greater than your guessed upper limit.
>
>And that's *without* compression.
box has 1.5 GB. I have trouble with not enough memory at times.
Adding another app might break its back.
Sincerely,
Gene Wirchenko
Jeff Higgins
May 29, 2012, 2:20:27 PM5/29/12
to
of time, patience, etc.
Daniel Pitts
May 29, 2012, 2:21:48 PM5/29/12
to
Daniel Pitts
May 29, 2012, 2:22:35 PM5/29/12
to
Jeff Higgins
May 29, 2012, 2:29:56 PM5/29/12
to
Jeff Higgins
May 29, 2012, 3:00:29 PM5/29/12
to
Lew
May 29, 2012, 5:03:10 PM5/29/12
to
Gene Wirchenko wrote:
You called my numbers "made up", but it turned out they were
*larger* than the real numbers.
You cite "a quarter of a million" words. Daniel counted roughly
*150%* of that in his word base.
My numbers were generous. Yours are not even significantly different,
and in fact are smaller than his. The numbers do show there is not
much problem, yet somehow you claim with no logic or reasoning or
different data that they do show a problem.
Clearly you are mistaken.
Daniel showed evidence from experimentation. His numbers jibe with
yours. Without compression, his data occupy roughly 5 MiB of memory.
Show the problem or withdraw the claim.
>> A modern desktop has more than enough memory to easily handle a quarter
>> *billion* words, which is a 100 times greater than your guessed upper limit.
>>
>> And that's *without* compression.
>
> Sure. If that is all that it does. My main (and older) desktop
> box has 1.5 GB. I have trouble with not enough memory at times.
> Adding another app might break its back.
Again, how much damage will < 5 MiB of data do to that system?
How about 50 MiB? That's *ten times* the number of words you might need to handle.
Without any compression.
You haven't shown a problem. You just chant, "The sky is falling!"
--
Lew
> Daniel Pitts wrote:
>
> [snip]
>
> >Are you arguing that a modern system can't handle that number of words?
>
> No. I simply stating that the real size of the problem is much
> bigger.
With no numbers that differ from Daniel's to back up your claim.
>
> [snip]
>
> >Are you arguing that a modern system can't handle that number of words?
>
> No. I simply stating that the real size of the problem is much
> bigger.
You called my numbers "made up", but it turned out they were
*larger* than the real numbers.
You cite "a quarter of a million" words. Daniel counted roughly
*150%* of that in his word base.
My numbers were generous. Yours are not even significantly different,
and in fact are smaller than his. The numbers do show there is not
much problem, yet somehow you claim with no logic or reasoning or
different data that they do show a problem.
Clearly you are mistaken.
Daniel showed evidence from experimentation. His numbers jibe with
yours. Without compression, his data occupy roughly 5 MiB of memory.
Show the problem or withdraw the claim.
>> A modern desktop has more than enough memory to easily handle a quarter
>> *billion* words, which is a 100 times greater than your guessed upper limit.
>>
>> And that's *without* compression.
>
> Sure. If that is all that it does. My main (and older) desktop
> box has 1.5 GB. I have trouble with not enough memory at times.
> Adding another app might break its back.
How about 50 MiB? That's *ten times* the number of words you might need to handle.
Without any compression.
You haven't shown a problem. You just chant, "The sky is falling!"
--
Lew
Gene Wirchenko
May 29, 2012, 5:44:11 PM5/29/12
to
On Tue, 29 May 2012 11:22:35 -0700, Daniel Pitts
that modern systems have many times that amount. Sure, they do, but
they also typically run more than one app. Assuming that your app can
use all of memory is not very friendly.
Sincerely,
Gene Wirchenko
<newsgrou...@virtualinfinity.net> wrote:
>On 5/29/12 11:17 AM, Gene Wirchenko wrote:
>> On Tue, 29 May 2012 09:55:02 -0700, Daniel Pitts
>> <newsgrou...@virtualinfinity.net> wrote:
>>
>> [snip]
>>
>>> Are you arguing that a modern system can't handle that number of words?
>>
>> No. I simply stating that the real size of the problem is much
>> bigger.
>>
>>> A modern desktop has more than enough memory to easily handle a quarter
>>> *billion* words, which is a 100 times greater than your guessed upper limit.
>>>
>>> And that's *without* compression.
>>
>> Sure. If that is all that it does. My main (and older) desktop
>> box has 1.5 GB. I have trouble with not enough memory at times.
>> Adding another app might break its back.
>On 5/29/12 11:17 AM, Gene Wirchenko wrote:
>> On Tue, 29 May 2012 09:55:02 -0700, Daniel Pitts
>> <newsgrou...@virtualinfinity.net> wrote:
>>
>> [snip]
>>
>>> Are you arguing that a modern system can't handle that number of words?
>>
>> No. I simply stating that the real size of the problem is much
>> bigger.
>>
>>> A modern desktop has more than enough memory to easily handle a quarter
>>> *billion* words, which is a 100 times greater than your guessed upper limit.
>>>
>>> And that's *without* compression.
>>
>> Sure. If that is all that it does. My main (and older) desktop
>> box has 1.5 GB. I have trouble with not enough memory at times.
>> Adding another app might break its back.
>Moving the goalpost again are we?
No. Someone claimed that the amount of memory needed was low and
that modern systems have many times that amount. Sure, they do, but
they also typically run more than one app. Assuming that your app can
use all of memory is not very friendly.
Sincerely,
Gene Wirchenko
Gene Wirchenko
May 29, 2012, 5:49:35 PM5/29/12
to
On Tue, 29 May 2012 14:03:10 -0700 (PDT), Lew <lewb...@gmail.com>
wrote:
>Gene Wirchenko wrote:
>> Daniel Pitts wrote:
>>
>> [snip]
>>
>> >Are you arguing that a modern system can't handle that number of words?
>>
>> No. I simply stating that the real size of the problem is much
>> bigger.
>
>With no numbers that differ from Daniel's to back up your claim.
>
>You called my numbers "made up", but it turned out they were
>*larger* than the real numbers.
>
>You cite "a quarter of a million" words. Daniel counted roughly
>*150%* of that in his word base.
Ah, selective reading.
For root forms, it was 1/4 million. With affixes -- and remember
that my first question was about them -- the figure was 3/4 million.
This is double what Daniel counted, and 3/4 million does not include
technical words, etc. Take a look at the *full* paragraph that I
quoted, not just the lowest number.
>My numbers were generous. Yours are not even significantly different,
>and in fact are smaller than his. The numbers do show there is not
>much problem, yet somehow you claim with no logic or reasoning or
>different data that they do show a problem.
Take another look at that paragraph I quoted. Really.
>Clearly you are mistaken.
>
>Daniel showed evidence from experimentation. His numbers jibe with
>yours. Without compression, his data occupy roughly 5 MiB of memory.
>
>Show the problem or withdraw the claim.
Read my statement of the problem.
>>> A modern desktop has more than enough memory to easily handle a quarter
>>> *billion* words, which is a 100 times greater than your guessed upper limit.
>>>
>>> And that's *without* compression.
>>
>> Sure. If that is all that it does. My main (and older) desktop
>> box has 1.5 GB. I have trouble with not enough memory at times.
>> Adding another app might break its back.
>
>Again, how much damage will < 5 MiB of data do to that system?
>
>How about 50 MiB? That's *ten times* the number of words you might need to handle.
>Without any compression.
Fine. My system is currently using 1547 MB of memory. It only
has 1536 MB. With some intensive uses, I have seen the commit go to
as high as about 2200 MB. My system crawls then. Using 50 MB more in
those circumstances would not be good.
>You haven't shown a problem. You just chant, "The sky is falling!"
I believe that I have. Handwaving the possibility away does not
make it go away.
Sincerely,
Gene Wirchenko
wrote:
>Gene Wirchenko wrote:
>> Daniel Pitts wrote:
>>
>> [snip]
>>
>> >Are you arguing that a modern system can't handle that number of words?
>>
>> No. I simply stating that the real size of the problem is much
>> bigger.
>
>With no numbers that differ from Daniel's to back up your claim.
>
>You called my numbers "made up", but it turned out they were
>*larger* than the real numbers.
>
>You cite "a quarter of a million" words. Daniel counted roughly
>*150%* of that in his word base.
For root forms, it was 1/4 million. With affixes -- and remember
that my first question was about them -- the figure was 3/4 million.
This is double what Daniel counted, and 3/4 million does not include
technical words, etc. Take a look at the *full* paragraph that I
quoted, not just the lowest number.
>My numbers were generous. Yours are not even significantly different,
>and in fact are smaller than his. The numbers do show there is not
>much problem, yet somehow you claim with no logic or reasoning or
>different data that they do show a problem.
>Clearly you are mistaken.
>
>Daniel showed evidence from experimentation. His numbers jibe with
>yours. Without compression, his data occupy roughly 5 MiB of memory.
>
>Show the problem or withdraw the claim.
>>> A modern desktop has more than enough memory to easily handle a quarter
>>> *billion* words, which is a 100 times greater than your guessed upper limit.
>>>
>>> And that's *without* compression.
>>
>> Sure. If that is all that it does. My main (and older) desktop
>> box has 1.5 GB. I have trouble with not enough memory at times.
>> Adding another app might break its back.
>
>Again, how much damage will < 5 MiB of data do to that system?
>
>How about 50 MiB? That's *ten times* the number of words you might need to handle.
>Without any compression.
has 1536 MB. With some intensive uses, I have seen the commit go to
as high as about 2200 MB. My system crawls then. Using 50 MB more in
those circumstances would not be good.
>You haven't shown a problem. You just chant, "The sky is falling!"
make it go away.
Sincerely,
Gene Wirchenko
Daniel Pitts
May 29, 2012, 6:23:50 PM5/29/12
to
package net.virtualinfinity.moby;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.Arrays;
public class WordTree {
WordNode start = new WordNode(-1);
public void addWord(String word) {
start.addWord(word);
}
public static void main(String[] args) throws IOException {
WordTree tree = new WordTree();
int wordsLoaded = 0;
for (String filename: args) {
System.out.println("Loading " + filename);
BufferedReader reader = new BufferedReader(new
FileReader(filename), 1024*256);
String line;
while ((line = reader.readLine()) != null) {
++wordsLoaded;
if ((wordsLoaded & 127) == 0) {
printStatus(wordsLoaded);
}
tree.addWord(line.trim());
}
System.gc();
printStatus(wordsLoaded);
System.out.println();
}
}
private static void printStatus(int wordsLoaded) {
System.out.print("\rWords loaded: " + wordsLoaded + ", Total
Memory used: " + Runtime.getRuntime().totalMemory() + ". ");
}
}
class WordNode {
private boolean terminal;
private final int value;
private WordNode[] next;
public WordNode(int ch) {
value = ch;
}
public void addWord(String word) {
if ("".equals(word)) {
terminal = true;
return;
}
final int ch = word.codePointAt(0);
getNext(ch).addWord(word.substring(Character.charCount(ch)));
}
private WordNode getNext(int ch) {
if (next == null) {
next = new WordNode[1];
next[0] = new WordNode(ch);
}
for (WordNode node: next) {
if (node.value == ch) {
return node;
}
}
next = Arrays.copyOf(next, next.length +1);
final WordNode newNode = new WordNode(ch);
next[next.length-1] = newNode;
return newNode;
}
}
------- Output -----
Loading compound-words.txt
Words loaded: 256772, Total Memory used: 120909824.
Loading often-mispelled.txt
Words loaded: 257138, Total Memory used: 121106432.
Loading english-most-frequent.txt
Words loaded: 258141, Total Memory used: 121106432.
Loading male-names.txt
Words loaded: 262038, Total Memory used: 121106432.
Loading female-names.txt
Words loaded: 266984, Total Memory used: 121106432.
Loading common-names.txt
Words loaded: 288970, Total Memory used: 121106432.
Loading common-dictionary.txt
Words loaded: 363520, Total Memory used: 127373312.
Loading official-scrabble-1st-edition.txt
Words loaded: 477329, Total Memory used: 129957888.
Loading official-scrabble-2nd-edition-delta.txt
Words loaded: 481489, Total Memory used: 129957888.
Daniel Pitts
May 29, 2012, 6:39:16 PM5/29/12
to
difference is ~ 42MB
So, loading 481k words takes up about 42MB. This is in java, which has a
fairly high overhead per string. And the implementation of my data
structure is also fairly naive as well.
Extrapolating that data to an extreme 2 million words, that would be
less than 200MB in memory.
My gut feeling beats your gut feeling, and my science proves it true. If
you are going to reply with a counter argument, please provide a
reproducible experiment to prove your argument. Otherwise, this
conversation is over.
Gene Wirchenko
May 29, 2012, 7:08:44 PM5/29/12
to
On Tue, 29 May 2012 15:39:16 -0700, Daniel Pitts
<newsgrou...@virtualinfinity.net> wrote:
[snip]
>BTW, if I check the memory usage before loading words and after, the
>difference is ~ 42MB
>
>So, loading 481k words takes up about 42MB. This is in java, which has a
>fairly high overhead per string. And the implementation of my data
>structure is also fairly naive as well.
So about 100 bytes per word.
>Extrapolating that data to an extreme 2 million words, that would be
>less than 200MB in memory.
Or about 100 MB for my SWAG of one million words.
>My gut feeling beats your gut feeling, and my science proves it true. If
It sure does. Lew's figures (up to 10 MB) were considerably
lower, and that is what I was objecting to. They seemed too low.
>you are going to reply with a counter argument, please provide a
>reproducible experiment to prove your argument. Otherwise, this
>conversation is over.
Actually, I started with a question, namely
Including all affixes?
and I have been trying to get a reasonable answer to it. I knew that
your word counts were low compared to others that I have seen and
wanted to know a realistic memory use figure for the *whole* English
language. You have provided a sufficiently good approximation. Thank
you.
Sincerely,
Gene Wirchenko
<newsgrou...@virtualinfinity.net> wrote:
[snip]
>BTW, if I check the memory usage before loading words and after, the
>difference is ~ 42MB
>
>So, loading 481k words takes up about 42MB. This is in java, which has a
>fairly high overhead per string. And the implementation of my data
>structure is also fairly naive as well.
>Extrapolating that data to an extreme 2 million words, that would be
>less than 200MB in memory.
>My gut feeling beats your gut feeling, and my science proves it true. If
lower, and that is what I was objecting to. They seemed too low.
>you are going to reply with a counter argument, please provide a
>reproducible experiment to prove your argument. Otherwise, this
>conversation is over.
Including all affixes?
and I have been trying to get a reasonable answer to it. I knew that
your word counts were low compared to others that I have seen and
wanted to know a realistic memory use figure for the *whole* English
language. You have provided a sufficiently good approximation. Thank
you.
Sincerely,
Gene Wirchenko
Lew
May 29, 2012, 9:25:45 PM5/29/12
to
Gene Wirchenko wrote:
footprint if the entire word list were in memory as naive Strings. I've been
talking about the footprint in storage (e.g., the SD card of a smartphone).
So, Gene, you have been misinterpreting my point.
There is little reason to hold the dictionary in memory at all times if you
are in a memory-constrained environment. If one does need to hold it
in memory, and one were worried about memory footprint, one would not
hold it in a memory-intensive, naive structure, in RAM all at once.
Compression exceeding 90% is typical with text. Assuming 75% compression,
a very reasonable and safe estimate, the data would occupy about 10 MB, just
as I said. That's if you keep it in memory in compressed form.
A disk-based solution would likely occupy only a few KB at a time.
Nice try to distort the issue into a scary monster, though.
--
Lew
> Daniel Pitts wrote:
>
> [snip]
>
>>BTW, if I check the memory usage before loading words and after, the
>>difference is ~ 42MB
>>
>>So, loading 481k words takes up about 42MB. This is in java, which has a
>>fairly high overhead per string. And the implementation of my data
>>structure is also fairly naive as well.
We've been talking apples and oranges. You refer here to the memory
>
> [snip]
>
>>BTW, if I check the memory usage before loading words and after, the
>>difference is ~ 42MB
>>
>>So, loading 481k words takes up about 42MB. This is in java, which has a
>>fairly high overhead per string. And the implementation of my data
>>structure is also fairly naive as well.
footprint if the entire word list were in memory as naive Strings. I've been
talking about the footprint in storage (e.g., the SD card of a smartphone).
So, Gene, you have been misinterpreting my point.
There is little reason to hold the dictionary in memory at all times if you
are in a memory-constrained environment. If one does need to hold it
in memory, and one were worried about memory footprint, one would not
hold it in a memory-intensive, naive structure, in RAM all at once.
Compression exceeding 90% is typical with text. Assuming 75% compression,
a very reasonable and safe estimate, the data would occupy about 10 MB, just
as I said. That's if you keep it in memory in compressed form.
A disk-based solution would likely occupy only a few KB at a time.
Nice try to distort the issue into a scary monster, though.
--
Lew
0 new messages