Re: Collection of strings available?

Path	csiph.com!eternal-september.org!feeder.eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups	comp.programming
Subject	Re: Collection of strings available?
Date	Sun, 21 Oct 2018 23:16:26 +0100
Organization	A noiseless patient Spider
Lines	41
Message-ID	<87va5v9c91.fsf@bsb.me.uk> (permalink)
References	<6ae449fc-a10c-44c0-8fd0-7243c4308687@googlegroups.com> <871s8jaul9.fsf@bsb.me.uk> <ac95bb7b-7774-45fe-aa3d-ef40c1746719@googlegroups.com>
Mime-Version	1.0
Content-Type	text/plain
Injection-Info	reader02.eternal-september.org; posting-host="36c69285fc7c7932b20a5e9b27245ac4"; logging-data="2189"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/uAuAx7jwsDPmDU4rGImIW8lczxWX5ObU="
Cancel-Lock	sha1:BQBuW5OZLTUCSt9dcidyJUWdUcQ= sha1:GcfBVvv1D6oUnAQ2QN6AO8jyGk8=
X-BSB-Auth	1.f32258381252e6dc12b4.20181021231626BST.87va5v9c91.fsf@bsb.me.uk
Xref	csiph.com comp.programming:9334

Show key headers only | View raw

Paul <pepstein5@gmail.com> writes:

> On Sunday, October 21, 2018 at 9:55:00 PM UTC+1, Ben Bacarisse wrote:
>> Paul <pepstein5@gmail.com> writes:
>> 
>> > As a coding exercise, I am writing a collection of string-matching
>> > algorithms -- for example Boyer Moore, Rabin-Karp etc.
>> >
>> > Does anyone know a handy collection of string patterns and texts to facilitate
>> > testing or do I need to generate the test data myself?
>> 
>> A handy source of large(ish) texts is Project Gutenberg.  If you need
>> larger (which you might for speed tests on a modern machine) you can
>> concatenate several books or collected works together.
>> 
>> You'll still have to generate test cases yourself.
>
> I don't think that English-language texts make good testcases for the
> algorithms because with English-language texts, the ultra-naive method of
> very simply comparing letter by letter is not likely to be
> inefficient.
>
> Better would be DNA-type strings.

The asymptotic complexity of the algorithms won't change based on the
kind of text.  You should be able to see a significant improvement in
performance between using a naive search and, say, Boyer Moore on
English text.

Obviously you will get different relative performance depending on the
actual string used and the frequency and distribution of the symbols, so
you might well want to have lots of different sources, but I'd include
English text as at least one.

> I suppose I'll have to generate them myself using rand().

And you might want to generate them not using rand()!  I.e. you will
probably want some very special test cases that are not at all random.

-- 
Ben.

Back to comp.programming | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

Collection of strings available? Paul <pepstein5@gmail.com> - 2018-10-21 13:05 -0700
  Re: Collection of strings available? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-10-21 21:54 +0100
    Re: Collection of strings available? Paul <pepstein5@gmail.com> - 2018-10-21 14:17 -0700
      Re: Collection of strings available? Sjouke Burry <burrynulnulfour@ppllaanneett.nnll> - 2018-10-21 23:23 +0200
      Re: Collection of strings available? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-10-21 23:16 +0100

csiph-web