Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.theory > #37173 > unrolled thread

skip: an O(n/m) pattern recognition algorithm

Back to article view | Back to comp.theory

Contents

  skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-27 15:40 -0700
    Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-29 01:19 -0700
      Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-30 05:43 -0700
        Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-30 05:55 -0700
          Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-30 06:28 -0700
            Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-30 06:40 -0700
        Re: skip: an O(n/m) pattern recognition algorithm Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-30 14:52 +0100
          Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-30 14:10 -0700
            Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-30 14:15 -0700
            Re: skip: an O(n/m) pattern recognition algorithm Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-30 22:45 +0100
              Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-02 13:30 -0700
            Re: skip: an O(n/m) pattern recognition algorithm Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-07-30 15:14 -0700
              Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-30 19:11 -0700
              Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-02 21:49 -0700
                Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-02 21:55 -0700
                  Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-02 22:10 -0700
                    Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-02 22:27 -0700
                      Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-02 23:00 -0700
                        Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-02 23:09 -0700
                    Re: skip: an O(n/m) pattern recognition algorithm Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-08-03 00:20 -0700
                      Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-03 00:48 -0700
                        Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-03 00:51 -0700
                          Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-03 00:56 -0700
                            Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-03 01:05 -0700
                              Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-03 01:18 -0700
                                Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-03 01:31 -0700
                                  Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-03 01:41 -0700
                                    Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-03 01:58 -0700
                                      Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-03 02:16 -0700
                                        Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-03 02:30 -0700
                                          Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-03 02:45 -0700
                                            Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-03 03:15 -0700
                          Re: skip: an O(n/m) pattern recognition algorithm Andy Walker <anw@cuboid.co.uk> - 2021-08-03 11:44 +0100
                            Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-03 04:04 -0700
                              Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-03 04:34 -0700
                              Re: skip: an O(n/m) pattern recognition algorithm Andy Walker <anw@cuboid.co.uk> - 2021-08-03 16:56 +0100
                                Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-03 11:25 -0700
                                  Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-03 13:16 -0700
                                    Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-04 00:51 -0700
                                      Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-04 01:18 -0700
                                        Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-04 01:27 -0700
                                          Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-04 01:34 -0700
                                            Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-04 01:40 -0700
                                              Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-04 01:46 -0700
                                              Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-04 01:51 -0700
                                                Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-04 02:15 -0700
                                                  Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-04 02:29 -0700
                                                    Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-04 02:48 -0700
                                                      Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-04 03:22 -0700
                                                        Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-04 03:50 -0700
                                        Re: skip: an O(n/m) pattern recognition algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-08-04 12:47 -0700
                                          Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-04 12:59 -0700
                                            Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-04 13:47 -0700

Page 1 of 3  [1] 2 3  Next page →

#37173 — skip: an O(n/m) pattern recognition algorithm

here is an O(n/m) pattern recognition algorithm, 
on alphabets size two or more.

in code below alphabet size A is two.

num is unsigned int
nums and numnums are arrays 
//////////////////////////////////////////////////////////////////
// the optimal average case recognition in base two or more identity program
num anum(num g, nums& small, nums& og)//lgm small numbers beginning at g multiplied, 
  //cost equals two lgm memrefs. lgm*lgA < 32 is a must. eg A=2, M must be < 64k.
{ num answer = one; for (num h = zero; h < og.lgsize(); h++) { when (g + h < small.size()) answer *= ((small[g + h]) + one); }
 return Lessone(answer);// lessone for zero based answers
}
num found = zero;
num skip(nums& og, nums& nize, num& A, numnums* work, numnums* cooljunknums)//ephemeral memory allocation
{// A==two.  when A = size of ASCII jdp discovered skip during a cs101 lecture by francine berman,1980.
 memrefs = zero;
 // pattern.size() /*64k is the upperbound on binary*/
 // Lessone(nize.size());  /*possibly a very large number*/
 when(og.size() < nize.size() + one) {
  //num lgM = og.lgsize();/*log base A of M*/
  num B = one;//A to the lgM
  for (num g = zero; B < og.size(); g++) { B = B * two; } //M <= B, tightly so
  //order of M small sets empty in the beginning then ordered from zero
  for (num g = (*work).size(); g < B; g++) { (*work).add((*cooljunknums).slop()); (*(*work).last()).clear();}
  //for our purposes, the pattern will never occur in stringeam.
  //if it does occur, halt. we must then do something...
  //so for our purposes, we are "proving" the pattern does nay occur. 
  //but, in fact, we crudely count number of pattern matches.
  //preprocessing
  //short sequences of adjacent letters of pattern, pieces of the puzzle
  for (num g = 0; g + og.lgsize() < og.size(); g++) {  /*at g collate lgM letters of pattern, interpret as a num*/
   (*(*work)[anum(g, og, og)]).add(g);
  }/*order of m lgm*/
  //main loop
  for (num j = 0; j + og.lgsize() < nize.size(); j = j + og.size() + one - (og.lgsize()))
  {/*at j*/
   /*for members of small set at work[answer]*/
   nums* smallset = (*work)[anum(j, nize, og)];
   for (num k = zero; k < (*smallset).size(); k++) {
    num beginat = j - (*smallset)[k];
    /*linear compare at beginat with pattern*/
    num there = one; /*assume*/
    for (num g = zero; g  < og.size(); g++) {
      when (nize[ beginat + g ] == og[ g ]) // #memrefs
        continue;
      there = zero; escLoop
    } 
    when(there) found++;
   }
  }/*order of N lgM over (M - lgM)*/
  //postprocessing could be identical to preprocessing
  for (num g = 0; g + og.lgsize() < og.size(); g++) {  /*at g collate lgM letters of pattern, interpret as a num*/
   (*(*work)[anum(g, og, og)]).slop();
  }/*order of m lgm*/
 }
 return memrefs;
}

[toc] | [next] | [standalone]

#37256

O(n/m) pattern recognition
sublinear instead of linear 

identity of short strings in a stream
identity of short strings in a stream is now sublinear 
reading of writing is now faster by an order of magnitude 
does anyone else understand skip?

good for deep logical reading + writing of letters
my favorite alphabet is 
the twenty seven letter momday alphabet 
abcdefghijklmnopqrstuvw yz0 
most words in the momday language 
are smaller than 27 letters 
given a line with n letters 
a good reader chunks 
the words of a line 
together 

anyway identity recognition is now sublinear 
good for cybersecurity of system kernels 

one of the main issues of skip on small strings is 
ephemeral memory allocation for small over time 
dependence on operating system for resources 
ephemeral allocation is worthy of more study 

On Tuesday, July 27, 2021 at 6:40:13 PM UTC-4, Daniel Pehoushek wrote:
> here is an O(n/m) pattern recognition algorithm, 
> on alphabets size two or more. 
> 
> in code below alphabet size A is two. 
> 
> num is unsigned int 
> nums and numnums are arrays 
> ////////////////////////////////////////////////////////////////// 
> // the optimal average case recognition in base two or more identity program 
> num anum(num g, nums& small, nums& og)//lgm small numbers beginning at g multiplied, 
> //cost equals two lgm memrefs. lgm*lgA < 32 is a must. eg A=2, M must be < 64k. 
> { num answer = one; for (num h = zero; h < og.lgsize(); h++) { when (g + h < small.size()) answer *= ((small[g + h]) + one); } 
> return Lessone(answer);// lessone for zero based answers 
> } 
> num found = zero; 
> num skip(nums& og, nums& nize, num& A, numnums* work, numnums* cooljunknums)//ephemeral memory allocation 
> {// A==two. when A = size of ASCII jdp discovered skip during a cs101 lecture by francine berman,1980. 
> memrefs = zero; 
> // pattern.size() /*64k is the upperbound on binary*/ 
> // Lessone(nize.size()); /*possibly a very large number*/ 
> when(og.size() < nize.size() + one) { 
> //num lgM = og.lgsize();/*log base A of M*/ 
> num B = one;//A to the lgM 
> for (num g = zero; B < og.size(); g++) { B = B * two; } //M <= B, tightly so 
> //order of M small sets empty in the beginning then ordered from zero 
> for (num g = (*work).size(); g < B; g++) { (*work).add((*cooljunknums).slop()); (*(*work).last()).clear();} 
> //for our purposes, the pattern will never occur in stringeam. 
> //if it does occur, halt. we must then do something... 
> //so for our purposes, we are "proving" the pattern does nay occur. 
> //but, in fact, we crudely count number of pattern matches. 
> //preprocessing 
> //short sequences of adjacent letters of pattern, pieces of the puzzle 
> for (num g = 0; g + og.lgsize() < og.size(); g++) { /*at g collate lgM letters of pattern, interpret as a num*/ 
> (*(*work)[anum(g, og, og)]).add(g); 
> }/*order of m lgm*/ 
> //main loop 
> for (num j = 0; j + og.lgsize() < nize.size(); j = j + og.size() + one - (og.lgsize())) 
> {/*at j*/ 
> /*for members of small set at work[answer]*/ 
> nums* smallset = (*work)[anum(j, nize, og)]; 
> for (num k = zero; k < (*smallset).size(); k++) { 
> num beginat = j - (*smallset)[k]; 
> /*linear compare at beginat with pattern*/ 
> num there = one; /*assume*/ 
> for (num g = zero; g < og.size(); g++) { 
> when (nize[ beginat + g ] == og[ g ]) // #memrefs 
> continue; 
> there = zero; escLoop 
> } 
> when(there) found++; 
> } 
> }/*order of N lgM over (M - lgM)*/ 
> //postprocessing could be identical to preprocessing 
> for (num g = 0; g + og.lgsize() < og.size(); g++) { /*at g collate lgM letters of pattern, interpret as a num*/ 
> (*(*work)[anum(g, og, og)]).slop(); 
> }/*order of m lgm*/ 
> } 
> return memrefs; 
> }

[toc] | [prev] | [next] | [standalone]

#37335

anyone interested in sublinear pattern matching?
O(n/m) is a giant leap from O(n+m)...
many applications.
is theory dead on this group?

On Thursday, July 29, 2021 at 4:19:46 AM UTC-4, Daniel Pehoushek wrote:
> O(n/m) pattern recognition 
> sublinear instead of linear 
> 
> identity of short strings in a stream 
> identity of short strings in a stream is now sublinear 
> reading of writing is now faster by an order of magnitude 
> does anyone else understand skip? 
> 
> good for deep logical reading + writing of letters 
> my favorite alphabet is 
> the twenty seven letter momday alphabet 
> abcdefghijklmnopqrstuvw yz0 
> most words in the momday language 
> are smaller than 27 letters 
> given a line with n letters 
> a good reader chunks 
> the words of a line 
> together 
> 
> anyway identity recognition is now sublinear 
> good for cybersecurity of system kernels 
> 
> one of the main issues of skip on small strings is 
> ephemeral memory allocation for small over time 
> dependence on operating system for resources 
> ephemeral allocation is worthy of more study
> On Tuesday, July 27, 2021 at 6:40:13 PM UTC-4, Daniel Pehoushek wrote: 
> > here is an O(n/m) pattern recognition algorithm, 
> > on alphabets size two or more. 
> > 
> > in code below alphabet size A is two. 
> > 
> > num is unsigned int 
> > nums and numnums are arrays 
> > ////////////////////////////////////////////////////////////////// 
> > // the optimal average case recognition in base two or more identity program 
> > num anum(num g, nums& small, nums& og)//lgm small numbers beginning at g multiplied, 
> > //cost equals two lgm memrefs. lgm*lgA < 32 is a must. eg A=2, M must be < 64k. 
> > { num answer = one; for (num h = zero; h < og.lgsize(); h++) { when (g + h < small.size()) answer *= ((small[g + h]) + one); } 
> > return Lessone(answer);// lessone for zero based answers 
> > } 
> > num found = zero; 
> > num skip(nums& og, nums& nize, num& A, numnums* work, numnums* cooljunknums)//ephemeral memory allocation 
> > {// A==two. when A = size of ASCII jdp discovered skip during a cs101 lecture by francine berman,1980. 
> > memrefs = zero; 
> > // pattern.size() /*64k is the upperbound on binary*/ 
> > // Lessone(nize.size()); /*possibly a very large number*/ 
> > when(og.size() < nize.size() + one) { 
> > //num lgM = og.lgsize();/*log base A of M*/ 
> > num B = one;//A to the lgM 
> > for (num g = zero; B < og.size(); g++) { B = B * two; } //M <= B, tightly so 
> > //order of M small sets empty in the beginning then ordered from zero 
> > for (num g = (*work).size(); g < B; g++) { (*work).add((*cooljunknums).slop()); (*(*work).last()).clear();} 
> > //for our purposes, the pattern will never occur in stringeam. 
> > //if it does occur, halt. we must then do something... 
> > //so for our purposes, we are "proving" the pattern does nay occur. 
> > //but, in fact, we crudely count number of pattern matches. 
> > //preprocessing 
> > //short sequences of adjacent letters of pattern, pieces of the puzzle 
> > for (num g = 0; g + og.lgsize() < og.size(); g++) { /*at g collate lgM letters of pattern, interpret as a num*/ 
> > (*(*work)[anum(g, og, og)]).add(g); 
> > }/*order of m lgm*/ 
> > //main loop 
> > for (num j = 0; j + og.lgsize() < nize.size(); j = j + og.size() + one - (og.lgsize())) 
> > {/*at j*/ 
> > /*for members of small set at work[answer]*/ 
> > nums* smallset = (*work)[anum(j, nize, og)]; 
> > for (num k = zero; k < (*smallset).size(); k++) { 
> > num beginat = j - (*smallset)[k]; 
> > /*linear compare at beginat with pattern*/ 
> > num there = one; /*assume*/ 
> > for (num g = zero; g < og.size(); g++) { 
> > when (nize[ beginat + g ] == og[ g ]) // #memrefs 
> > continue; 
> > there = zero; escLoop 
> > } 
> > when(there) found++; 
> > } 
> > }/*order of N lgM over (M - lgM)*/ 
> > //postprocessing could be identical to preprocessing 
> > for (num g = 0; g + og.lgsize() < og.size(); g++) { /*at g collate lgM letters of pattern, interpret as a num*/ 
> > (*(*work)[anum(g, og, og)]).slop(); 
> > }/*order of m lgm*/ 
> > } 
> > return memrefs; 
> > }

[toc] | [prev] | [next] | [standalone]

#37336

cyber security: identity of kernal programs
general identity questions
two dimensional pattern matching
et cetera 

the key performance detail is ephemeral memory allocation 
to keep from hassling the os for small pieces of memory.

good on base two, for nlgm/m performance 
compared with n+m for knuth morris pratt.

initial version published at combinatorial pattern matching 1998 (CPM98).
the chinese use a version of skip to do censorship.
daniel

On Friday, July 30, 2021 at 8:43:29 AM UTC-4, Daniel Pehoushek wrote:
> anyone interested in sublinear pattern matching? 
> O(n/m) is a giant leap from O(n+m)... 
> many applications. 
> is theory dead on this group?
> On Thursday, July 29, 2021 at 4:19:46 AM UTC-4, Daniel Pehoushek wrote: 
> > O(n/m) pattern recognition 
> > sublinear instead of linear 
> > 
> > identity of short strings in a stream 
> > identity of short strings in a stream is now sublinear 
> > reading of writing is now faster by an order of magnitude 
> > does anyone else understand skip? 
> > 
> > good for deep logical reading + writing of letters 
> > my favorite alphabet is 
> > the twenty seven letter momday alphabet 
> > abcdefghijklmnopqrstuvw yz0 
> > most words in the momday language 
> > are smaller than 27 letters 
> > given a line with n letters 
> > a good reader chunks 
> > the words of a line 
> > together 
> > 
> > anyway identity recognition is now sublinear 
> > good for cybersecurity of system kernels 
> > 
> > one of the main issues of skip on small strings is 
> > ephemeral memory allocation for small over time 
> > dependence on operating system for resources 
> > ephemeral allocation is worthy of more study 
> > On Tuesday, July 27, 2021 at 6:40:13 PM UTC-4, Daniel Pehoushek wrote: 
> > > here is an O(n/m) pattern recognition algorithm, 
> > > on alphabets size two or more. 
> > > 
> > > in code below alphabet size A is two. 
> > > 
> > > num is unsigned int 
> > > nums and numnums are arrays 
> > > ////////////////////////////////////////////////////////////////// 
> > > // the optimal average case recognition in base two or more identity program 
> > > num anum(num g, nums& small, nums& og)//lgm small numbers beginning at g multiplied, 
> > > //cost equals two lgm memrefs. lgm*lgA < 32 is a must. eg A=2, M must be < 64k. 
> > > { num answer = one; for (num h = zero; h < og.lgsize(); h++) { when (g + h < small.size()) answer *= ((small[g + h]) + one); } 
> > > return Lessone(answer);// lessone for zero based answers 
> > > } 
> > > num found = zero; 
> > > num skip(nums& og, nums& nize, num& A, numnums* work, numnums* cooljunknums)//ephemeral memory allocation 
> > > {// A==two. when A = size of ASCII jdp discovered skip during a cs101 lecture by francine berman,1980. 
> > > memrefs = zero; 
> > > // pattern.size() /*64k is the upperbound on binary*/ 
> > > // Lessone(nize.size()); /*possibly a very large number*/ 
> > > when(og.size() < nize.size() + one) { 
> > > //num lgM = og.lgsize();/*log base A of M*/ 
> > > num B = one;//A to the lgM 
> > > for (num g = zero; B < og.size(); g++) { B = B * two; } //M <= B, tightly so 
> > > //order of M small sets empty in the beginning then ordered from zero 
> > > for (num g = (*work).size(); g < B; g++) { (*work).add((*cooljunknums).slop()); (*(*work).last()).clear();} 
> > > //for our purposes, the pattern will never occur in stringeam. 
> > > //if it does occur, halt. we must then do something... 
> > > //so for our purposes, we are "proving" the pattern does nay occur. 
> > > //but, in fact, we crudely count number of pattern matches. 
> > > //preprocessing 
> > > //short sequences of adjacent letters of pattern, pieces of the puzzle 
> > > for (num g = 0; g + og.lgsize() < og.size(); g++) { /*at g collate lgM letters of pattern, interpret as a num*/ 
> > > (*(*work)[anum(g, og, og)]).add(g); 
> > > }/*order of m lgm*/ 
> > > //main loop 
> > > for (num j = 0; j + og.lgsize() < nize.size(); j = j + og.size() + one - (og.lgsize())) 
> > > {/*at j*/ 
> > > /*for members of small set at work[answer]*/ 
> > > nums* smallset = (*work)[anum(j, nize, og)]; 
> > > for (num k = zero; k < (*smallset).size(); k++) { 
> > > num beginat = j - (*smallset)[k]; 
> > > /*linear compare at beginat with pattern*/ 
> > > num there = one; /*assume*/ 
> > > for (num g = zero; g < og.size(); g++) { 
> > > when (nize[ beginat + g ] == og[ g ]) // #memrefs 
> > > continue; 
> > > there = zero; escLoop 
> > > } 
> > > when(there) found++; 
> > > } 
> > > }/*order of N lgM over (M - lgM)*/ 
> > > //postprocessing could be identical to preprocessing 
> > > for (num g = 0; g + og.lgsize() < og.size(); g++) { /*at g collate lgM letters of pattern, interpret as a num*/ 
> > > (*(*work)[anum(g, og, og)]).slop(); 
> > > }/*order of m lgm*/ 
> > > } 
> > > return memrefs; 
> > > }

[toc] | [prev] | [next] | [standalone]

#37338

google uses string matching 
skip search is an order of magnitude better.

On Friday, July 30, 2021 at 8:55:39 AM UTC-4, Daniel Pehoushek wrote:
> cyber security: identity of kernal programs 
> general identity questions 
> two dimensional pattern matching 
> et cetera 
> 
> the key performance detail is ephemeral memory allocation 
> to keep from hassling the os for small pieces of memory. 
> 
> good on base two, for nlgm/m performance 
> compared with n+m for knuth morris pratt. 
> 
> initial version published at combinatorial pattern matching 1998 (CPM98). 
> the chinese use a version of skip to do censorship. 
> daniel
> On Friday, July 30, 2021 at 8:43:29 AM UTC-4, Daniel Pehoushek wrote: 
> > anyone interested in sublinear pattern matching? 
> > O(n/m) is a giant leap from O(n+m)... 
> > many applications. 
> > is theory dead on this group? 
> > On Thursday, July 29, 2021 at 4:19:46 AM UTC-4, Daniel Pehoushek wrote: 
> > > O(n/m) pattern recognition 
> > > sublinear instead of linear 
> > > 
> > > identity of short strings in a stream 
> > > identity of short strings in a stream is now sublinear 
> > > reading of writing is now faster by an order of magnitude 
> > > does anyone else understand skip? 
> > > 
> > > good for deep logical reading + writing of letters 
> > > my favorite alphabet is 
> > > the twenty seven letter momday alphabet 
> > > abcdefghijklmnopqrstuvw yz0 
> > > most words in the momday language 
> > > are smaller than 27 letters 
> > > given a line with n letters 
> > > a good reader chunks 
> > > the words of a line 
> > > together 
> > > 
> > > anyway identity recognition is now sublinear 
> > > good for cybersecurity of system kernels 
> > > 
> > > one of the main issues of skip on small strings is 
> > > ephemeral memory allocation for small over time 
> > > dependence on operating system for resources 
> > > ephemeral allocation is worthy of more study 
> > > On Tuesday, July 27, 2021 at 6:40:13 PM UTC-4, Daniel Pehoushek wrote: 
> > > > here is an O(n/m) pattern recognition algorithm, 
> > > > on alphabets size two or more. 
> > > > 
> > > > in code below alphabet size A is two. 
> > > > 
> > > > num is unsigned int 
> > > > nums and numnums are arrays 
> > > > ////////////////////////////////////////////////////////////////// 
> > > > // the optimal average case recognition in base two or more identity program 
> > > > num anum(num g, nums& small, nums& og)//lgm small numbers beginning at g multiplied, 
> > > > //cost equals two lgm memrefs. lgm*lgA < 32 is a must. eg A=2, M must be < 64k. 
> > > > { num answer = one; for (num h = zero; h < og.lgsize(); h++) { when (g + h < small.size()) answer *= ((small[g + h]) + one); } 
> > > > return Lessone(answer);// lessone for zero based answers 
> > > > } 
> > > > num found = zero; 
> > > > num skip(nums& og, nums& nize, num& A, numnums* work, numnums* cooljunknums)//ephemeral memory allocation 
> > > > {// A==two. when A = size of ASCII jdp discovered skip during a cs101 lecture by francine berman,1980. 
> > > > memrefs = zero; 
> > > > // pattern.size() /*64k is the upperbound on binary*/ 
> > > > // Lessone(nize.size()); /*possibly a very large number*/ 
> > > > when(og.size() < nize.size() + one) { 
> > > > //num lgM = og.lgsize();/*log base A of M*/ 
> > > > num B = one;//A to the lgM 
> > > > for (num g = zero; B < og.size(); g++) { B = B * two; } //M <= B, tightly so 
> > > > //order of M small sets empty in the beginning then ordered from zero 
> > > > for (num g = (*work).size(); g < B; g++) { (*work).add((*cooljunknums).slop()); (*(*work).last()).clear();} 
> > > > //for our purposes, the pattern will never occur in stringeam. 
> > > > //if it does occur, halt. we must then do something... 
> > > > //so for our purposes, we are "proving" the pattern does nay occur. 
> > > > //but, in fact, we crudely count number of pattern matches. 
> > > > //preprocessing 
> > > > //short sequences of adjacent letters of pattern, pieces of the puzzle 
> > > > for (num g = 0; g + og.lgsize() < og.size(); g++) { /*at g collate lgM letters of pattern, interpret as a num*/ 
> > > > (*(*work)[anum(g, og, og)]).add(g); 
> > > > }/*order of m lgm*/ 
> > > > //main loop 
> > > > for (num j = 0; j + og.lgsize() < nize.size(); j = j + og.size() + one - (og.lgsize())) 
> > > > {/*at j*/ 
> > > > /*for members of small set at work[answer]*/ 
> > > > nums* smallset = (*work)[anum(j, nize, og)]; 
> > > > for (num k = zero; k < (*smallset).size(); k++) { 
> > > > num beginat = j - (*smallset)[k]; 
> > > > /*linear compare at beginat with pattern*/ 
> > > > num there = one; /*assume*/ 
> > > > for (num g = zero; g < og.size(); g++) { 
> > > > when (nize[ beginat + g ] == og[ g ]) // #memrefs 
> > > > continue; 
> > > > there = zero; escLoop 
> > > > } 
> > > > when(there) found++; 
> > > > } 
> > > > }/*order of N lgM over (M - lgM)*/ 
> > > > //postprocessing could be identical to preprocessing 
> > > > for (num g = 0; g + og.lgsize() < og.size(); g++) { /*at g collate lgM letters of pattern, interpret as a num*/ 
> > > > (*(*work)[anum(g, og, og)]).slop(); 
> > > > }/*order of m lgm*/ 
> > > > } 
> > > > return memrefs; 
> > > > }

[toc] | [prev] | [next] | [standalone]

#37340

O(n/m) for decades been availble instead of O(n+m).
i am not saying computer scientists are stupid but 
i just submitted a totally correct oracle for 
model counting and universal truth 
but i could not overcome the committees ignorance.

so now i am presenting a few weeks of ancient work 
on recognition, identity, string matching, pattern matching, 
cybersecurity, whatever you want to call it.
an order of magnitude improvement 
over known results.
does anyone care?
daniel


On Friday, July 30, 2021 at 9:28:38 AM UTC-4, Daniel Pehoushek wrote:
> google uses string matching 
> skip search is an order of magnitude better.
> On Friday, July 30, 2021 at 8:55:39 AM UTC-4, Daniel Pehoushek wrote: 
> > cyber security: identity of kernal programs 
> > general identity questions 
> > two dimensional pattern matching 
> > et cetera 
> > 
> > the key performance detail is ephemeral memory allocation 
> > to keep from hassling the os for small pieces of memory. 
> > 
> > good on base two, for nlgm/m performance 
> > compared with n+m for knuth morris pratt. 
> > 
> > initial version published at combinatorial pattern matching 1998 (CPM98). 
> > the chinese use a version of skip to do censorship. 
> > daniel 
> > On Friday, July 30, 2021 at 8:43:29 AM UTC-4, Daniel Pehoushek wrote: 
> > > anyone interested in sublinear pattern matching? 
> > > O(n/m) is a giant leap from O(n+m)... 
> > > many applications. 
> > > is theory dead on this group? 
> > > On Thursday, July 29, 2021 at 4:19:46 AM UTC-4, Daniel Pehoushek wrote: 
> > > > O(n/m) pattern recognition 
> > > > sublinear instead of linear 
> > > > 
> > > > identity of short strings in a stream 
> > > > identity of short strings in a stream is now sublinear 
> > > > reading of writing is now faster by an order of magnitude 
> > > > does anyone else understand skip? 
> > > > 
> > > > good for deep logical reading + writing of letters 
> > > > my favorite alphabet is 
> > > > the twenty seven letter momday alphabet 
> > > > abcdefghijklmnopqrstuvw yz0 
> > > > most words in the momday language 
> > > > are smaller than 27 letters 
> > > > given a line with n letters 
> > > > a good reader chunks 
> > > > the words of a line 
> > > > together 
> > > > 
> > > > anyway identity recognition is now sublinear 
> > > > good for cybersecurity of system kernels 
> > > > 
> > > > one of the main issues of skip on small strings is 
> > > > ephemeral memory allocation for small over time 
> > > > dependence on operating system for resources 
> > > > ephemeral allocation is worthy of more study 
> > > > On Tuesday, July 27, 2021 at 6:40:13 PM UTC-4, Daniel Pehoushek wrote: 
> > > > > here is an O(n/m) pattern recognition algorithm, 
> > > > > on alphabets size two or more. 
> > > > > 
> > > > > in code below alphabet size A is two. 
> > > > > 
> > > > > num is unsigned int 
> > > > > nums and numnums are arrays 
> > > > > ////////////////////////////////////////////////////////////////// 
> > > > > // the optimal average case recognition in base two or more identity program 
> > > > > num anum(num g, nums& small, nums& og)//lgm small numbers beginning at g multiplied, 
> > > > > //cost equals two lgm memrefs. lgm*lgA < 32 is a must. eg A=2, M must be < 64k. 
> > > > > { num answer = one; for (num h = zero; h < og.lgsize(); h++) { when (g + h < small.size()) answer *= ((small[g + h]) + one); } 
> > > > > return Lessone(answer);// lessone for zero based answers 
> > > > > } 
> > > > > num found = zero; 
> > > > > num skip(nums& og, nums& nize, num& A, numnums* work, numnums* cooljunknums)//ephemeral memory allocation 
> > > > > {// A==two. when A = size of ASCII jdp discovered skip during a cs101 lecture by francine berman,1980. 
> > > > > memrefs = zero; 
> > > > > // pattern.size() /*64k is the upperbound on binary*/ 
> > > > > // Lessone(nize.size()); /*possibly a very large number*/ 
> > > > > when(og.size() < nize.size() + one) { 
> > > > > //num lgM = og.lgsize();/*log base A of M*/ 
> > > > > num B = one;//A to the lgM 
> > > > > for (num g = zero; B < og.size(); g++) { B = B * two; } //M <= B, tightly so 
> > > > > //order of M small sets empty in the beginning then ordered from zero 
> > > > > for (num g = (*work).size(); g < B; g++) { (*work).add((*cooljunknums).slop()); (*(*work).last()).clear();} 
> > > > > //for our purposes, the pattern will never occur in stringeam. 
> > > > > //if it does occur, halt. we must then do something... 
> > > > > //so for our purposes, we are "proving" the pattern does nay occur. 
> > > > > //but, in fact, we crudely count number of pattern matches. 
> > > > > //preprocessing 
> > > > > //short sequences of adjacent letters of pattern, pieces of the puzzle 
> > > > > for (num g = 0; g + og.lgsize() < og.size(); g++) { /*at g collate lgM letters of pattern, interpret as a num*/ 
> > > > > (*(*work)[anum(g, og, og)]).add(g); 
> > > > > }/*order of m lgm*/ 
> > > > > //main loop 
> > > > > for (num j = 0; j + og.lgsize() < nize.size(); j = j + og.size() + one - (og.lgsize())) 
> > > > > {/*at j*/ 
> > > > > /*for members of small set at work[answer]*/ 
> > > > > nums* smallset = (*work)[anum(j, nize, og)]; 
> > > > > for (num k = zero; k < (*smallset).size(); k++) { 
> > > > > num beginat = j - (*smallset)[k]; 
> > > > > /*linear compare at beginat with pattern*/ 
> > > > > num there = one; /*assume*/ 
> > > > > for (num g = zero; g < og.size(); g++) { 
> > > > > when (nize[ beginat + g ] == og[ g ]) // #memrefs 
> > > > > continue; 
> > > > > there = zero; escLoop 
> > > > > } 
> > > > > when(there) found++; 
> > > > > } 
> > > > > }/*order of N lgM over (M - lgM)*/ 
> > > > > //postprocessing could be identical to preprocessing 
> > > > > for (num g = 0; g + og.lgsize() < og.size(); g++) { /*at g collate lgM letters of pattern, interpret as a num*/ 
> > > > > (*(*work)[anum(g, og, og)]).slop(); 
> > > > > }/*order of m lgm*/ 
> > > > > } 
> > > > > return memrefs; 
> > > > > }

[toc] | [prev] | [next] | [standalone]

#37342

Daniel Pehoushek <pehoushek1@gmail.com> writes:

> anyone interested in sublinear pattern matching?

Post something about it.

> O(n/m) is a giant leap from O(n+m)...

I think you have something wrong there.  The formal meaning of big O is
not 100% obvious when the function is of more than one variable, so
maybe you are using the notation in a slightly odd way?

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#37367

On Friday, July 30, 2021 at 9:52:22 AM UTC-4, Ben Bacarisse wrote:
> Daniel Pehoushek <pehou...@gmail.com> writes: 
> 
> > anyone interested in sublinear pattern matching?
> Post something about it.
> > O(n/m) is a giant leap from O(n+m)...
> I think you have something wrong there. The formal meaning of big O is 
> not 100% obvious when the function is of more than one variable, so 
> maybe you are using the notation in a slightly odd way? 
> 
> -- 
> Ben.

no, i really do mean sublinear, n/m.
obviously growing in efficiency as m grows and n remains large.

similar to O(N*M) for graphs with smaller M than N^2...

[toc] | [prev] | [next] | [standalone]

#37368

picture looking for a 31 bit boolean string somewhere in one million bits
skip would take perhaps 200,000 memory references 
to do the job instead of 1,000,031.

On Friday, July 30, 2021 at 5:10:58 PM UTC-4, Daniel Pehoushek wrote:
> On Friday, July 30, 2021 at 9:52:22 AM UTC-4, Ben Bacarisse wrote: 
> > Daniel Pehoushek <pehou...@gmail.com> writes: 
> > 
> > > anyone interested in sublinear pattern matching? 
> > Post something about it. 
> > > O(n/m) is a giant leap from O(n+m)... 
> > I think you have something wrong there. The formal meaning of big O is 
> > not 100% obvious when the function is of more than one variable, so 
> > maybe you are using the notation in a slightly odd way? 
> > 
> > -- 
> > Ben.
> no, i really do mean sublinear, n/m. 
> obviously growing in efficiency as m grows and n remains large. 
> 
> similar to O(N*M) for graphs with smaller M than N^2...

[toc] | [prev] | [next] | [standalone]

#37370

Daniel Pehoushek <pehoushek1@gmail.com> writes:

> On Friday, July 30, 2021 at 9:52:22 AM UTC-4, Ben Bacarisse wrote:
>> Daniel Pehoushek <pehou...@gmail.com> writes: 
>> 
>> > anyone interested in sublinear pattern matching?
>> Post something about it.
>> > O(n/m) is a giant leap from O(n+m)...
>> I think you have something wrong there. The formal meaning of big O is 
>> not 100% obvious when the function is of more than one variable, so 
>> maybe you are using the notation in a slightly odd way? 
>
> no, i really do mean sublinear, n/m.
> obviously growing in efficiency as m grows and n remains large.

What is the asymptotic cost of matching a pattern of length n in a
string of length n?  Does the complexity depend on whether the match
succeeds or fails?  Have you got an actual formula for the number of
step the algorithm takes for patterns of length m in strings of length
n?  An actual formula would about the complexity of multi-variable Big O
notation.  Is the algorithm published?

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#37505

On Friday, July 30, 2021 at 5:45:43 PM UTC-4, Ben Bacarisse wrote:
> Daniel Pehoushek <pehou...@gmail.com> writes: 
> 
> > On Friday, July 30, 2021 at 9:52:22 AM UTC-4, Ben Bacarisse wrote: 
> >> Daniel Pehoushek <pehou...@gmail.com> writes: 
> >> 
> >> > anyone interested in sublinear pattern matching? 
> >> Post something about it. 
> >> > O(n/m) is a giant leap from O(n+m)... 
> >> I think you have something wrong there. The formal meaning of big O is 
> >> not 100% obvious when the function is of more than one variable, so 
> >> maybe you are using the notation in a slightly odd way? 
> >
> > no, i really do mean sublinear, n/m. 
> > obviously growing in efficiency as m grows and n remains large.
> What is the asymptotic cost of matching a pattern of length n in a 
> string of length n? Does the complexity depend on whether the match 
> succeeds or fails? Have you got an actual formula for the number of 
> step the algorithm takes for patterns of length m in strings of length 
> n? An actual formula would about the complexity of multi-variable Big O 
> notation. Is the algorithm published? 
> 
> -- 
> Ben.
that could become a special case in poor code in my opinion.
in present skip search when m is a jth power of the alphabet size 
the running time is 2nj + j.  or merely nj.
daniel

[toc] | [prev] | [next] | [standalone]

#37376

On Friday, 30 July 2021 at 22:10:58 UTC+1, pehou...@gmail.com wrote:
> On Friday, July 30, 2021 at 9:52:22 AM UTC-4, Ben Bacarisse wrote: 
> > Daniel Pehoushek <pehou...@gmail.com> writes: 
> > 
> > > anyone interested in sublinear pattern matching? 
> > Post something about it. 
> > > O(n/m) is a giant leap from O(n+m)... 
> > I think you have something wrong there. The formal meaning of big O is 
> > not 100% obvious when the function is of more than one variable, so 
> > maybe you are using the notation in a slightly odd way? 
> > 
> > -- 
> > Ben.
> no, i really do mean sublinear, n/m. 
> obviously growing in efficiency as m grows and n remains large. 
> 
> similar to O(N*M) for graphs with smaller M than N^2...
>
I see. The haystack is n, the needle is m bytes.
Because you skip, the larger m is, the fewer comparisons you need.

Obviously the data has to have certain characteristics or it has to be
pre-processed in some way for this to work. But that's often the
case. The haystack is highly non-random, and the chance of it
containing the needle is much higher than would be predicted from
length alone. 

[toc] | [prev] | [next] | [standalone]

#37393

generally right.
the algorithm is (lgm is log base alphabet of m)
time: mlgm + nlgm/(m-lgm+1) + mlgm
including preprocessing, main loop, garbage collection.
in vaguely big oh reasoning, it is n/m.
good on alphabets of size two is noteworthy.

i published at combinatorial pattern matching 1998 (CPM98) 
my coauthor butchered the paper but the runtime holds.
good for cybersecurity problems. fast.
i believe that on random strings
the average case behavior is optimal.

On Friday, July 30, 2021 at 6:14:17 PM UTC-4, malcolm.ar...@gmail.com wrote:
> On Friday, 30 July 2021 at 22:10:58 UTC+1, pehou...@gmail.com wrote: 
> > On Friday, July 30, 2021 at 9:52:22 AM UTC-4, Ben Bacarisse wrote: 
> > > Daniel Pehoushek <pehou...@gmail.com> writes: 
> > > 
> > > > anyone interested in sublinear pattern matching? 
> > > Post something about it. 
> > > > O(n/m) is a giant leap from O(n+m)... 
> > > I think you have something wrong there. The formal meaning of big O is 
> > > not 100% obvious when the function is of more than one variable, so 
> > > maybe you are using the notation in a slightly odd way? 
> > > 
> > > -- 
> > > Ben. 
> > no, i really do mean sublinear, n/m. 
> > obviously growing in efficiency as m grows and n remains large. 
> > 
> > similar to O(N*M) for graphs with smaller M than N^2... 
> >
> I see. The haystack is n, the needle is m bytes. 
> Because you skip, the larger m is, the fewer comparisons you need. 
> 
> Obviously the data has to have certain characteristics or it has to be 
> pre-processed in some way for this to work. But that's often the 
> case. The haystack is highly non-random, and the chance of it 
> containing the needle is much higher than would be predicted from 
> length alone.

[toc] | [prev] | [next] | [standalone]

#37519

On Friday, July 30, 2021 at 6:14:17 PM UTC-4, malcolm.ar...@gmail.com wrote:
> On Friday, 30 July 2021 at 22:10:58 UTC+1, pehou...@gmail.com wrote: 
> > On Friday, July 30, 2021 at 9:52:22 AM UTC-4, Ben Bacarisse wrote: 
> > > Daniel Pehoushek <pehou...@gmail.com> writes: 
> > > 
> > > > anyone interested in sublinear pattern matching? 
> > > Post something about it. 
> > > > O(n/m) is a giant leap from O(n+m)... 
> > > I think you have something wrong there. The formal meaning of big O is 
> > > not 100% obvious when the function is of more than one variable, so 
> > > maybe you are using the notation in a slightly odd way? 
> > > 
> > > -- 
> > > Ben. 
> > no, i really do mean sublinear, n/m. 
> > obviously growing in efficiency as m grows and n remains large. 
> > 
> > similar to O(N*M) for graphs with smaller M than N^2... 
> >
> I see. The haystack is n, the needle is m bytes. 
> Because you skip, the larger m is, the fewer comparisons you need. 
> 
> Obviously the data has to have certain characteristics or it has to be 
> pre-processed in some way for this to work. But that's often the 
> case. The haystack is highly non-random, and the chance of it 
> containing the needle is much higher than would be predicted from 
> length alone.

i have really only considered random (pseudo random of course. "random" is just a theory...) letters, 
and really only thought much about base two.  so probabilities of patterns are (1/2)^m.  and really 
i only care about memrefs, the finds that a google search might produce are irrelevant to study.  

lets restrict m to the jth power of two to make analysis look good. 
there is preprocessing, at mj.
the main loop, if you call the m-j+1 skip size m, is nj/m.
then garbage collection is mj.
mj + nj/m + mj... just nj/m for me.

so when m = square root of nj we have a cusp point.
rather invariant of alphabet size 

i suppose search for precise lines of letters in large files is one of the best applications
invariance of alphabet size is metaphysical knowledge 

think about searching for good parts of verses in scripture 
as time passes in civilization generally so do scriptures grow
locate all copies of any bible verse in civilizations writing is fast with skip
to measure of some comprehension of the words of god 

other good applications similar to googling bible verses?
daniel little d

[toc] | [prev] | [next] | [standalone]

#37520

On Tuesday, August 3, 2021 at 12:49:39 AM UTC-4, Daniel Pehoushek wrote:
> On Friday, July 30, 2021 at 6:14:17 PM UTC-4, malcolm.ar...@gmail.com wrote:
> > On Friday, 30 July 2021 at 22:10:58 UTC+1, pehou...@gmail.com wrote: 
> > > On Friday, July 30, 2021 at 9:52:22 AM UTC-4, Ben Bacarisse wrote: 
> > > > Daniel Pehoushek <pehou...@gmail.com> writes: 
> > > > 
> > > > > anyone interested in sublinear pattern matching? 
> > > > Post something about it. 
> > > > > O(n/m) is a giant leap from O(n+m)... 
> > > > I think you have something wrong there. The formal meaning of big O is 
> > > > not 100% obvious when the function is of more than one variable, so 
> > > > maybe you are using the notation in a slightly odd way? 
> > > > 
> > > > -- 
> > > > Ben. 
> > > no, i really do mean sublinear, n/m. 
> > > obviously growing in efficiency as m grows and n remains large. 
> > > 
> > > similar to O(N*M) for graphs with smaller M than N^2... 
> > > 
> > I see. The haystack is n, the needle is m bytes. 
> > Because you skip, the larger m is, the fewer comparisons you need. 
> > 
> > Obviously the data has to have certain characteristics or it has to be 
> > pre-processed in some way for this to work. But that's often the 
> > case. The haystack is highly non-random, and the chance of it 
> > containing the needle is much higher than would be predicted from 
> > length alone.
> i have really only considered random (pseudo random of course. "random" is just a theory...) letters, 
> and really only thought much about base two. so probabilities of patterns are (1/2)^m. and really 
> i only care about memrefs, the finds that a google search might produce are irrelevant to study. 
> 
> lets restrict m to the jth power of two to make analysis look good. 
> there is preprocessing, at mj. 
> the main loop, if you call the m-j+1 skip size m, is nj/m. 
> then garbage collection is mj. 
> mj + nj/m + mj... just nj/m for me. 
> 
> so when m = square root of nj we have a cusp point. 
> rather invariant of alphabet size 
> 
> i suppose search for precise lines of letters in large files is one of the best applications 
> invariance of alphabet size is metaphysical knowledge 
> 
> think about searching for good parts of verses in scripture 
> as time passes in civilization generally so do scriptures grow 
> locate all copies of any bible verse in civilizations writing is fast with skip 
> to measure of some comprehension of the words of god 
> 
> other good applications similar to googling bible verses? 
> daniel little d

my favorite is "forgive them father, they know not what they do"
and on some perhaps overly conservative planets,
the inquisitions of academic ignorance 
about universal truths 
being in qspace 
in the boolean
space time
hierarchy

[toc] | [prev] | [next] | [standalone]

#37523

onward
what about pictures?
consider nxn bitmaps of zero and one where n is a power of the alphabet size
then search for pattern sized mxm where m is power of two
i would take the most distinguished line of m letters of pattern
search bitmap in time nxn/m for all occurs 
is this optimal in theory?
my guess is yes, 
invariant of pizel details...
those could be deep.

daniel

On Tuesday, August 3, 2021 at 12:55:44 AM UTC-4, Daniel Pehoushek wrote:
> On Tuesday, August 3, 2021 at 12:49:39 AM UTC-4, Daniel Pehoushek wrote: 
> > On Friday, July 30, 2021 at 6:14:17 PM UTC-4, malcolm.ar...@gmail.com wrote: 
> > > On Friday, 30 July 2021 at 22:10:58 UTC+1, pehou...@gmail.com wrote: 
> > > > On Friday, July 30, 2021 at 9:52:22 AM UTC-4, Ben Bacarisse wrote: 
> > > > > Daniel Pehoushek <pehou...@gmail.com> writes: 
> > > > > 
> > > > > > anyone interested in sublinear pattern matching? 
> > > > > Post something about it. 
> > > > > > O(n/m) is a giant leap from O(n+m)... 
> > > > > I think you have something wrong there. The formal meaning of big O is 
> > > > > not 100% obvious when the function is of more than one variable, so 
> > > > > maybe you are using the notation in a slightly odd way? 
> > > > > 
> > > > > -- 
> > > > > Ben. 
> > > > no, i really do mean sublinear, n/m. 
> > > > obviously growing in efficiency as m grows and n remains large. 
> > > > 
> > > > similar to O(N*M) for graphs with smaller M than N^2... 
> > > > 
> > > I see. The haystack is n, the needle is m bytes. 
> > > Because you skip, the larger m is, the fewer comparisons you need. 
> > > 
> > > Obviously the data has to have certain characteristics or it has to be 
> > > pre-processed in some way for this to work. But that's often the 
> > > case. The haystack is highly non-random, and the chance of it 
> > > containing the needle is much higher than would be predicted from 
> > > length alone. 
> > i have really only considered random (pseudo random of course. "random" is just a theory...) letters, 
> > and really only thought much about base two. so probabilities of patterns are (1/2)^m. and really 
> > i only care about memrefs, the finds that a google search might produce are irrelevant to study. 
> > 
> > lets restrict m to the jth power of two to make analysis look good. 
> > there is preprocessing, at mj. 
> > the main loop, if you call the m-j+1 skip size m, is nj/m. 
> > then garbage collection is mj. 
> > mj + nj/m + mj... just nj/m for me. 
> > 
> > so when m = square root of nj we have a cusp point. 
> > rather invariant of alphabet size 
> > 
> > i suppose search for precise lines of letters in large files is one of the best applications 
> > invariance of alphabet size is metaphysical knowledge 
> > 
> > think about searching for good parts of verses in scripture 
> > as time passes in civilization generally so do scriptures grow 
> > locate all copies of any bible verse in civilizations writing is fast with skip 
> > to measure of some comprehension of the words of god 
> > 
> > other good applications similar to googling bible verses? 
> > daniel little d
> my favorite is "forgive them father, they know not what they do" 
> and on some perhaps overly conservative planets, 
> the inquisitions of academic ignorance 
> about universal truths 
> being in qspace 
> in the boolean 
> space time 
> hierarchy

[toc] | [prev] | [next] | [standalone]

#37525

for a two dimensional sample 
that i as author of bob value highly 
say pizel size is alphabet size 
with forty five line verse

// operation three +s bobs   
// mental truth core system 
inline joy abinitio(num w) { 
  t_r_e_e += ones[w]; count++; }   

// ones to zeroes for shore 
inline num yaystonays(num z){
  when(t_r_e_e&(one<<z)){
    t_r_e_e&=diagovreason[z];
    count=countdown[count];
    env::zeesva[env::zeesvg++]=usiv+z;
    when(one==count)
      return ergo();}
  return count;}

// unity with solution 
// oh of degree of verty
// nineteen cpu steps 
num ergo(){ // the bob has newly just one way
  nums& m=*oneways.v[unity(t_r_e_e,wyde())];
  num y=zero;num g=zero;
  while(g<m.y) // for all adjacent vertys 
    when((*env::allBobs.v[(y=m.v[g++])>>siv]).yaystonays(y&sivones)) 
    continue; // bail when bottom 
    else return(*env::allBobs.v[zero]).yaystonays(zero);
  return one;}

// logicians algorithm
// vital for 
// finish counting
inline joy faith( num w) {
  when((count + one) < wyde()) 
    for ( num g = zero; eon() && g < numbols.size(); g++) // for all soubs
      when(isnay((w&(one<<g))?(w&diagovreason[g]):(w+(one<<g))))
        (*env::allBobs[soubs[g]]).yaystonays(rempos(g,w)); // resolution
  for(num g=zero;eon()&&g<soups.size();g++)
  {num ug=intosoups[g];num apw=addpos(ug,w);
   Bob* supe=env::allBobs[soups[g]];
   (*supe).yaystonays(apw);
   (*supe).yaystonays(apw+(one<<ug));}}

sayvum inline num addpos(num p,num s){return((s>>p)<<(p+one))+(s&tautologies[p]); }//add position p to num s
sayvum inline num rempos(num p,num s){return((s>>(p+one))<<p)+(s&tautologies[p]); }//remove position p num s
static inline num unity(num t,num numw){when(numw<five){return oneoffour[t];} // heart of search returns a light number
for(num w=zero;w<numw;w++)when(t&(one<<w)){return w;}return zero;}//otherwise test every w


On Tuesday, August 3, 2021 at 1:10:06 AM UTC-4, Daniel Pehoushek wrote:
> onward 
> what about pictures? 
> consider nxn bitmaps of zero and one where n is a power of the alphabet size 
> then search for pattern sized mxm where m is power of two 
> i would take the most distinguished line of m letters of pattern 
> search bitmap in time nxn/m for all occurs 
> is this optimal in theory? 
> my guess is yes, 
> invariant of pizel details... 
> those could be deep. 
> 
> daniel
> On Tuesday, August 3, 2021 at 12:55:44 AM UTC-4, Daniel Pehoushek wrote: 
> > On Tuesday, August 3, 2021 at 12:49:39 AM UTC-4, Daniel Pehoushek wrote: 
> > > On Friday, July 30, 2021 at 6:14:17 PM UTC-4, malcolm.ar...@gmail.com wrote: 
> > > > On Friday, 30 July 2021 at 22:10:58 UTC+1, pehou...@gmail.com wrote: 
> > > > > On Friday, July 30, 2021 at 9:52:22 AM UTC-4, Ben Bacarisse wrote: 
> > > > > > Daniel Pehoushek <pehou...@gmail.com> writes: 
> > > > > > 
> > > > > > > anyone interested in sublinear pattern matching? 
> > > > > > Post something about it. 
> > > > > > > O(n/m) is a giant leap from O(n+m)... 
> > > > > > I think you have something wrong there. The formal meaning of big O is 
> > > > > > not 100% obvious when the function is of more than one variable, so 
> > > > > > maybe you are using the notation in a slightly odd way? 
> > > > > > 
> > > > > > -- 
> > > > > > Ben. 
> > > > > no, i really do mean sublinear, n/m. 
> > > > > obviously growing in efficiency as m grows and n remains large. 
> > > > > 
> > > > > similar to O(N*M) for graphs with smaller M than N^2... 
> > > > > 
> > > > I see. The haystack is n, the needle is m bytes. 
> > > > Because you skip, the larger m is, the fewer comparisons you need. 
> > > > 
> > > > Obviously the data has to have certain characteristics or it has to be 
> > > > pre-processed in some way for this to work. But that's often the 
> > > > case. The haystack is highly non-random, and the chance of it 
> > > > containing the needle is much higher than would be predicted from 
> > > > length alone. 
> > > i have really only considered random (pseudo random of course. "random" is just a theory...) letters, 
> > > and really only thought much about base two. so probabilities of patterns are (1/2)^m. and really 
> > > i only care about memrefs, the finds that a google search might produce are irrelevant to study. 
> > > 
> > > lets restrict m to the jth power of two to make analysis look good. 
> > > there is preprocessing, at mj. 
> > > the main loop, if you call the m-j+1 skip size m, is nj/m. 
> > > then garbage collection is mj. 
> > > mj + nj/m + mj... just nj/m for me. 
> > > 
> > > so when m = square root of nj we have a cusp point. 
> > > rather invariant of alphabet size 
> > > 
> > > i suppose search for precise lines of letters in large files is one of the best applications 
> > > invariance of alphabet size is metaphysical knowledge 
> > > 
> > > think about searching for good parts of verses in scripture 
> > > as time passes in civilization generally so do scriptures grow 
> > > locate all copies of any bible verse in civilizations writing is fast with skip 
> > > to measure of some comprehension of the words of god 
> > > 
> > > other good applications similar to googling bible verses? 
> > > daniel little d 
> > my favorite is "forgive them father, they know not what they do" 
> > and on some perhaps overly conservative planets, 
> > the inquisitions of academic ignorance 
> > about universal truths 
> > being in qspace 
> > in the boolean 
> > space time 
> > hierarchy

[toc] | [prev] | [next] | [standalone]

#37529

On Tuesday, August 3, 2021 at 1:27:08 AM UTC-4, Daniel Pehoushek wrote:
> for a two dimensional sample 
> that i as author of bob value highly 
> say pizel size is alphabet size 
> with forty five line verse 
> 
> // operation three +s bobs 
> // mental truth core system 
> inline joy abinitio(num w) { 
> t_r_e_e += ones[w]; count++; } 
> 
> // ones to zeroes for shore 
> inline num yaystonays(num z){ 
> when(t_r_e_e&(one<<z)){ 
> t_r_e_e&=diagovreason[z]; 
> count=countdown[count]; 
> env::zeesva[env::zeesvg++]=usiv+z; 
> when(one==count) 
> return ergo();} 
> return count;} 
> 
> // unity with solution 
> // oh of degree of verty 
> // nineteen cpu steps 
> num ergo(){ // the bob has newly just one way 
> nums& m=*oneways.v[unity(t_r_e_e,wyde())]; 
> num y=zero;num g=zero; 
> while(g<m.y) // for all adjacent vertys 
> when((*env::allBobs.v[(y=m.v[g++])>>siv]).yaystonays(y&sivones)) 
> continue; // bail when bottom 
> else return(*env::allBobs.v[zero]).yaystonays(zero); 
> return one;} 
> 
> // logicians algorithm 
> // vital for 
> // finish counting 
> inline joy faith( num w) { 
> when((count + one) < wyde()) 
> for ( num g = zero; eon() && g < numbols.size(); g++) // for all soubs 
> when(isnay((w&(one<<g))?(w&diagovreason[g]):(w+(one<<g)))) 
> (*env::allBobs[soubs[g]]).yaystonays(rempos(g,w)); // resolution 
> for(num g=zero;eon()&&g<soups.size();g++) 
> {num ug=intosoups[g];num apw=addpos(ug,w); 
> Bob* supe=env::allBobs[soups[g]]; 
> (*supe).yaystonays(apw); 
> (*supe).yaystonays(apw+(one<<ug));}} 
> 
> sayvum inline num addpos(num p,num s){return((s>>p)<<(p+one))+(s&tautologies[p]); }//add position p to num s 
> sayvum inline num rempos(num p,num s){return((s>>(p+one))<<p)+(s&tautologies[p]); }//remove position p num s 
> static inline num unity(num t,num numw){when(numw<five){return oneoffour[t];} // heart of search returns a light number 
> for(num w=zero;w<numw;w++)when(t&(one<<w)){return w;}return zero;}//otherwise test every w
> On Tuesday, August 3, 2021 at 1:10:06 AM UTC-4, Daniel Pehoushek wrote: 
> > onward 
> > what about pictures? 
> > consider nxn bitmaps of zero and one where n is a power of the alphabet size 
> > then search for pattern sized mxm where m is power of two 
> > i would take the most distinguished line of m letters of pattern 
> > search bitmap in time nxn/m for all occurs 
> > is this optimal in theory? 
> > my guess is yes, 
> > invariant of pizel details... 
> > those could be deep. 
> > 
> > daniel 
> > On Tuesday, August 3, 2021 at 12:55:44 AM UTC-4, Daniel Pehoushek wrote: 
> > > On Tuesday, August 3, 2021 at 12:49:39 AM UTC-4, Daniel Pehoushek wrote: 
> > > > On Friday, July 30, 2021 at 6:14:17 PM UTC-4, malcolm.ar...@gmail.com wrote: 
> > > > > On Friday, 30 July 2021 at 22:10:58 UTC+1, pehou...@gmail.com wrote: 
> > > > > > On Friday, July 30, 2021 at 9:52:22 AM UTC-4, Ben Bacarisse wrote: 
> > > > > > > Daniel Pehoushek <pehou...@gmail.com> writes: 
> > > > > > > 
> > > > > > > > anyone interested in sublinear pattern matching? 
> > > > > > > Post something about it. 
> > > > > > > > O(n/m) is a giant leap from O(n+m)... 
> > > > > > > I think you have something wrong there. The formal meaning of big O is 
> > > > > > > not 100% obvious when the function is of more than one variable, so 
> > > > > > > maybe you are using the notation in a slightly odd way? 
> > > > > > > 
> > > > > > > -- 
> > > > > > > Ben. 
> > > > > > no, i really do mean sublinear, n/m. 
> > > > > > obviously growing in efficiency as m grows and n remains large. 
> > > > > > 
> > > > > > similar to O(N*M) for graphs with smaller M than N^2... 
> > > > > > 
> > > > > I see. The haystack is n, the needle is m bytes. 
> > > > > Because you skip, the larger m is, the fewer comparisons you need. 
> > > > > 
> > > > > Obviously the data has to have certain characteristics or it has to be 
> > > > > pre-processed in some way for this to work. But that's often the 
> > > > > case. The haystack is highly non-random, and the chance of it 
> > > > > containing the needle is much higher than would be predicted from 
> > > > > length alone. 
> > > > i have really only considered random (pseudo random of course. "random" is just a theory...) letters, 
> > > > and really only thought much about base two. so probabilities of patterns are (1/2)^m. and really 
> > > > i only care about memrefs, the finds that a google search might produce are irrelevant to study. 
> > > > 
> > > > lets restrict m to the jth power of two to make analysis look good. 
> > > > there is preprocessing, at mj. 
> > > > the main loop, if you call the m-j+1 skip size m, is nj/m. 
> > > > then garbage collection is mj. 
> > > > mj + nj/m + mj... just nj/m for me. 
> > > > 
> > > > so when m = square root of nj we have a cusp point. 
> > > > rather invariant of alphabet size 
> > > > 
> > > > i suppose search for precise lines of letters in large files is one of the best applications 
> > > > invariance of alphabet size is metaphysical knowledge 
> > > > 
> > > > think about searching for good parts of verses in scripture 
> > > > as time passes in civilization generally so do scriptures grow 
> > > > locate all copies of any bible verse in civilizations writing is fast with skip 
> > > > to measure of some comprehension of the words of god 
> > > > 
> > > > other good applications similar to googling bible verses? 
> > > > daniel little d 
> > > my favorite is "forgive them father, they know not what they do" 
> > > and on some perhaps overly conservative planets, 
> > > the inquisitions of academic ignorance 
> > > about universal truths 
> > > being in qspace 
> > > in the boolean 
> > > space time 
> > > hierarchy

for three dimensions 
use nnn and mmm
take most distinguished mm plane of mmm cube 
search for mm in nnn in time nnn/mm

so three dimensional pattern matching is 
on the order of space size nnn over m*m
on a cube pattern sized mmm 
with arbitrary pizel size 
daniel

[toc] | [prev] | [next] | [standalone]

#37530

On Tuesday, August 3, 2021 at 2:00:27 AM UTC-4, Daniel Pehoushek wrote:
> On Tuesday, August 3, 2021 at 1:27:08 AM UTC-4, Daniel Pehoushek wrote: 
> > for a two dimensional sample 
> > that i as author of bob value highly 
> > say pizel size is alphabet size 
> > with forty five line verse 
> > 
> > // operation three +s bobs 
> > // mental truth core system 
> > inline joy abinitio(num w) { 
> > t_r_e_e += ones[w]; count++; } 
> > 
> > // ones to zeroes for shore 
> > inline num yaystonays(num z){ 
> > when(t_r_e_e&(one<<z)){ 
> > t_r_e_e&=diagovreason[z]; 
> > count=countdown[count]; 
> > env::zeesva[env::zeesvg++]=usiv+z; 
> > when(one==count) 
> > return ergo();} 
> > return count;} 
> > 
> > // unity with solution 
> > // oh of degree of verty 
> > // nineteen cpu steps 
> > num ergo(){ // the bob has newly just one way 
> > nums& m=*oneways.v[unity(t_r_e_e,wyde())]; 
> > num y=zero;num g=zero; 
> > while(g<m.y) // for all adjacent vertys 
> > when((*env::allBobs.v[(y=m.v[g++])>>siv]).yaystonays(y&sivones)) 
> > continue; // bail when bottom 
> > else return(*env::allBobs.v[zero]).yaystonays(zero); 
> > return one;} 
> > 
> > // logicians algorithm 
> > // vital for 
> > // finish counting 
> > inline joy faith( num w) { 
> > when((count + one) < wyde()) 
> > for ( num g = zero; eon() && g < numbols.size(); g++) // for all soubs 
> > when(isnay((w&(one<<g))?(w&diagovreason[g]):(w+(one<<g)))) 
> > (*env::allBobs[soubs[g]]).yaystonays(rempos(g,w)); // resolution 
> > for(num g=zero;eon()&&g<soups.size();g++) 
> > {num ug=intosoups[g];num apw=addpos(ug,w); 
> > Bob* supe=env::allBobs[soups[g]]; 
> > (*supe).yaystonays(apw); 
> > (*supe).yaystonays(apw+(one<<ug));}} 
> > 
> > sayvum inline num addpos(num p,num s){return((s>>p)<<(p+one))+(s&tautologies[p]); }//add position p to num s 
> > sayvum inline num rempos(num p,num s){return((s>>(p+one))<<p)+(s&tautologies[p]); }//remove position p num s 
> > static inline num unity(num t,num numw){when(numw<five){return oneoffour[t];} // heart of search returns a light number 
> > for(num w=zero;w<numw;w++)when(t&(one<<w)){return w;}return zero;}//otherwise test every w 
> > On Tuesday, August 3, 2021 at 1:10:06 AM UTC-4, Daniel Pehoushek wrote: 
> > > onward 
> > > what about pictures? 
> > > consider nxn bitmaps of zero and one where n is a power of the alphabet size 
> > > then search for pattern sized mxm where m is power of two 
> > > i would take the most distinguished line of m letters of pattern 
> > > search bitmap in time nxn/m for all occurs 
> > > is this optimal in theory? 
> > > my guess is yes, 
> > > invariant of pizel details... 
> > > those could be deep. 
> > > 
> > > daniel 
> > > On Tuesday, August 3, 2021 at 12:55:44 AM UTC-4, Daniel Pehoushek wrote: 
> > > > On Tuesday, August 3, 2021 at 12:49:39 AM UTC-4, Daniel Pehoushek wrote: 
> > > > > On Friday, July 30, 2021 at 6:14:17 PM UTC-4, malcolm.ar...@gmail.com wrote: 
> > > > > > On Friday, 30 July 2021 at 22:10:58 UTC+1, pehou...@gmail.com wrote: 
> > > > > > > On Friday, July 30, 2021 at 9:52:22 AM UTC-4, Ben Bacarisse wrote: 
> > > > > > > > Daniel Pehoushek <pehou...@gmail.com> writes: 
> > > > > > > > 
> > > > > > > > > anyone interested in sublinear pattern matching? 
> > > > > > > > Post something about it. 
> > > > > > > > > O(n/m) is a giant leap from O(n+m)... 
> > > > > > > > I think you have something wrong there. The formal meaning of big O is 
> > > > > > > > not 100% obvious when the function is of more than one variable, so 
> > > > > > > > maybe you are using the notation in a slightly odd way? 
> > > > > > > > 
> > > > > > > > -- 
> > > > > > > > Ben. 
> > > > > > > no, i really do mean sublinear, n/m. 
> > > > > > > obviously growing in efficiency as m grows and n remains large. 
> > > > > > > 
> > > > > > > similar to O(N*M) for graphs with smaller M than N^2... 
> > > > > > > 
> > > > > > I see. The haystack is n, the needle is m bytes. 
> > > > > > Because you skip, the larger m is, the fewer comparisons you need. 
> > > > > > 
> > > > > > Obviously the data has to have certain characteristics or it has to be 
> > > > > > pre-processed in some way for this to work. But that's often the 
> > > > > > case. The haystack is highly non-random, and the chance of it 
> > > > > > containing the needle is much higher than would be predicted from 
> > > > > > length alone. 
> > > > > i have really only considered random (pseudo random of course. "random" is just a theory...) letters, 
> > > > > and really only thought much about base two. so probabilities of patterns are (1/2)^m. and really 
> > > > > i only care about memrefs, the finds that a google search might produce are irrelevant to study. 
> > > > > 
> > > > > lets restrict m to the jth power of two to make analysis look good. 
> > > > > there is preprocessing, at mj. 
> > > > > the main loop, if you call the m-j+1 skip size m, is nj/m. 
> > > > > then garbage collection is mj. 
> > > > > mj + nj/m + mj... just nj/m for me. 
> > > > > 
> > > > > so when m = square root of nj we have a cusp point. 
> > > > > rather invariant of alphabet size 
> > > > > 
> > > > > i suppose search for precise lines of letters in large files is one of the best applications 
> > > > > invariance of alphabet size is metaphysical knowledge 
> > > > > 
> > > > > think about searching for good parts of verses in scripture 
> > > > > as time passes in civilization generally so do scriptures grow 
> > > > > locate all copies of any bible verse in civilizations writing is fast with skip 
> > > > > to measure of some comprehension of the words of god 
> > > > > 
> > > > > other good applications similar to googling bible verses? 
> > > > > daniel little d 
> > > > my favorite is "forgive them father, they know not what they do" 
> > > > and on some perhaps overly conservative planets, 
> > > > the inquisitions of academic ignorance 
> > > > about universal truths 
> > > > being in qspace 
> > > > in the boolean 
> > > > space time 
> > > > hierarchy
> for three dimensions 
> use nnn and mmm 
> take most distinguished mm plane of mmm cube 
> search for mm in nnn in time nnn/mm 
> 
> so three dimensional pattern matching is 
> on the order of space size nnn over m*m 
> on a cube pattern sized mmm 
> with arbitrary pizel size 
> daniel

in four dimensions space nnnn pattern mmmm
choose most distinguished cube mmm of mmmm 

time to find all occurs is nnnn/mmm 
with arbitrary pizel size
daniel

[toc] | [prev] | [next] | [standalone]

#37531

On Tuesday, 3 August 2021 at 06:10:06 UTC+1, pehou...@gmail.com wrote:
> onward 
> what about pictures? 
> consider nxn bitmaps of zero and one where n is a power of the alphabet size 
> then search for pattern sized mxm where m is power of two 
> i would take the most distinguished line of m letters of pattern 
> search bitmap in time nxn/m for all occurs 
> is this optimal in theory? 
> my guess is yes, 
> invariant of pizel details... 
> those could be deep. 
> 
"z" is the least common letter in English text. So if you are searching for the
string "zigzag" you could scan the string looking for zs, then check the character
four places along. If you are expecting the string "zigzag" then you've almost
certainly got your match.

There are other techniques you can use. One is to build a suffix tree of the 
entire input. The suffix tree is quite expensive to construct. But once you
have it, all your searches are O(N needle).

I'm not sure how you would extend the suffix tree idea to two dimensions,
but it's maybe possible.

[toc] | [prev] | [next] | [standalone]

Page 1 of 3  [1] 2 3  Next page →

Back to top | Article view | comp.theory

csiph-web