Path: csiph.com!eternal-september.org!feeder.eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail From: Ben Bacarisse 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> References: <6ae449fc-a10c-44c0-8fd0-7243c4308687@googlegroups.com> <871s8jaul9.fsf@bsb.me.uk> 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 Paul writes: > On Sunday, October 21, 2018 at 9:55:00 PM UTC+1, Ben Bacarisse wrote: >> Paul 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.