< 1610323369 251301 :rain1!~My_user_n@unaffiliated/rain1 QUIT :Quit: WeeChat 3.0
> 1610325552 820119 PRIVMSG #esoteric :14[[07Clue (oklopol)/Quicksort14]]4 M10 02https://esolangs.org/w/index.php?diff=79929&oldid=20726 5* 03PythonshellDebugwindow 5* (+6) 10Cat, rm redundant nowiki tag
> 1610325610 215253 PRIVMSG #esoteric :14[[07Clue (oklopol)/SKI calculus14]]4 M10 02https://esolangs.org/w/index.php?diff=79930&oldid=20724 5* 03PythonshellDebugwindow 5* (+6) 10Cat, rm redundant nowiki tag
< 1610327267 970888 :copumpkin!~copumpkin@068-186-082-088.res.spectrum.com JOIN :#esoteric
< 1610328295 332171 :ArthurStrong!~ArthurStr@188.163.100.177 QUIT :Quit: leaving
< 1610328823 326315 :copumpkin!~copumpkin@068-186-082-088.res.spectrum.com QUIT :Changing host
< 1610328823 326370 :copumpkin!~copumpkin@unaffiliated/copumpkin JOIN :#esoteric
< 1610337600 335233 :Taneb!~Taneb@2001:41c8:51:10d:aaaa:0:aaaa:0 QUIT :Quit: I seem to have stopped.
< 1610337690 317379 :Taneb!~Taneb@2001:41c8:51:10d:aaaa:0:aaaa:0 JOIN :#esoteric
< 1610339774 145718 :harha!~harha@ns356919.ip-91-121-144.eu QUIT :Quit: ZNC 1.8.2 - https://znc.in
< 1610340415 822549 :harha_!~harha@ns356919.ip-91-121-144.eu JOIN :#esoteric
< 1610347057 592176 :MDude!~MDude@71.50.47.112 QUIT :Quit: Going offline, see ya! (www.adiirc.com)
< 1610347245 861867 :Sgeo!~Sgeo@ool-18b98aa4.dyn.optonline.net QUIT :Read error: Connection reset by peer
< 1610347544 146822 :Sgeo!~Sgeo@ool-18b98aa4.dyn.optonline.net JOIN :#esoteric
< 1610348595 259880 :Lykaina!~lyka@unaffiliated/schrodingerscat PRIVMSG #esoteric :wb Sgeo 
< 1610348609 759948 :Sgeo!~Sgeo@ool-18b98aa4.dyn.optonline.net PRIVMSG #esoteric :ty
< 1610348650 222586 :Lykaina!~lyka@unaffiliated/schrodingerscat PRIVMSG #esoteric :can't sleep either?
< 1610348878 683709 :Sgeo!~Sgeo@ool-18b98aa4.dyn.optonline.net PRIVMSG #esoteric :I usually go to sleep later than this. Probably not a good habit
< 1610349021 259604 :int-e!~noone@int-e.eu PRIVMSG #esoteric :@time Sgeo 
< 1610349022 245754 :lambdabot!~lambdabot@haskell/bot/lambdabot PRIVMSG #esoteric :Local time for Sgeo is Mon Jan 11 02:10:20
< 1610352503 977485 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :I tried to reconstruct KMP string search from "memory" (I never actually looked at the details so it's not really memory), and ended up with something else instead.
< 1610352522 789389 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :With a lookup table of size |pattern| * 256
< 1610353420 958990 :Sgeo!~Sgeo@ool-18b98aa4.dyn.optonline.net QUIT :Read error: Connection reset by peer
< 1610354361 856711 :LKoen!~LKoen@152.172.9.109.rev.sfr.net JOIN :#esoteric
< 1610354579 908147 :imode!~imode@unaffiliated/imode JOIN :#esoteric
< 1610354874 686051 :int-e!~noone@int-e.eu PRIVMSG #esoteric :shachaf: Yeah KMP builds a very compactly represented NFA, not a DFA.
< 1610354925 153664 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Right, I saw something about that.
< 1610354991 635748 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Or, hmm, this book says that KMP uses a deterministic automaton.
< 1610355018 117932 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :And compares it to shift-and which uses a nondeterministic automaton, it says.
< 1610355023 79680 :int-e!~noone@int-e.eu PRIVMSG #esoteric :KMP has epsilon transitions
< 1610355071 214266 :int-e!~noone@int-e.eu PRIVMSG #esoteric :Hrm.
< 1610355086 788819 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Epsilon transitions? I must be thinking of something else then.
< 1610355110 365468 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Or maybe it's just about how you're thinking of it.
< 1610355113 392011 :int-e!~noone@int-e.eu PRIVMSG #esoteric :Maybe I'm taking a too detailed view on KMP.
< 1610355181 144590 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :If you have /.*pattern/, you can think of the NFA where state 0 has a transition to state 1 on p, and also to state 0 on every character.
< 1610355192 248476 :int-e!~noone@int-e.eu PRIVMSG #esoteric :In that view, each time you compare a letter from the haystack with a letter from the needle, a transition is made.
< 1610355253 661882 :int-e!~noone@int-e.eu PRIVMSG #esoteric :And each time these are not equal, the haystack letter is not consumed... so that makes it an epsilon transition to my mind.
< 1610355272 148313 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Aha, I see.
< 1610355277 263616 :int-e!~noone@int-e.eu PRIVMSG #esoteric :But then again it lacks the annoying property of NFAs that you have to keep track of several states...
< 1610355302 747239 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :I was sort of thinking you operate by always taking one character at a time and doing your transitions, which is why I ended up with a DFA.
< 1610355309 827220 :int-e!~noone@int-e.eu PRIVMSG #esoteric :So it's a weird beast inbetween :)
< 1610355316 303797 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :But the trick is that it's allowed to choose not to consume characters.
< 1610355329 705499 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :So a single character can take multiple transitions (possibly all the way back to 0).
< 1610355332 821676 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Is that right?
< 1610355338 749742 :int-e!~noone@int-e.eu PRIVMSG #esoteric :Yes.
< 1610355375 161210 :int-e!~noone@int-e.eu PRIVMSG #esoteric :Mainly this was/is me trying to make sense of the table that KMP builds.
< 1610355376 513609 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Neato, that makes sense.
< 1610355384 903994 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :I think I vaguely remember something about that now.
< 1610355391 383169 :int-e!~noone@int-e.eu PRIVMSG #esoteric :Which if it is viewed as a DFA, is hard.
< 1610355442 849730 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :But it's still guaranteed to take linear time.
< 1610355489 81192 :int-e!~noone@int-e.eu PRIVMSG #esoteric :Oh yes. Each DFA transition takes amortized constant time.
< 1610355525 428824 :int-e!~noone@int-e.eu PRIVMSG #esoteric :But you almost certainly know that.
< 1610355539 682085 :myname!~myname@2001:41d0:1:766f::1 PRIVMSG #esoteric :why is that, though?
< 1610355544 367766 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :I "know" it but it's not immediately obvious why.
< 1610355550 133629 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :I guess it's some typical amortized argument.
< 1610355561 605331 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :To be able to jump back you must have gone forward some number of steps.
< 1610355570 962299 :int-e!~noone@int-e.eu PRIVMSG #esoteric :Each epsilon transition goes back in the needle, so is paid for by a previous transition that advanced in the needle.
< 1610355618 486232 :int-e!~noone@int-e.eu PRIVMSG #esoteric :So that's your cost per character: Advance the needle, plus a potential epsilon transition that skips back.
< 1610355735 322693 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Right, that's the sort of thing I meant.
< 1610355784 610278 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :So, hmm, you get at most 2n transitions or something?
< 1610355791 525884 :int-e!~noone@int-e.eu PRIVMSG #esoteric :(and then, of course, there's building the table)
< 1610355809 965074 :int-e!~noone@int-e.eu PRIVMSG #esoteric :shachaf: right
< 1610355835 810637 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Where "n" is the length of the haystack, not the needle, despite the confusing name.
< 1610355874 674490 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Anyway, this book doesn't actually get into the details of KMP. It says it's mainly useful for short needles, and there are better algorithms for those.
< 1610355931 685512 :int-e!~noone@int-e.eu PRIVMSG #esoteric :Hmm. Somehow I've never studied Boyer-Moore.
< 1610355988 444078 :int-e!~noone@int-e.eu PRIVMSG #esoteric :Beyond the very basic idea (skip ahead a full needle's length; if you're lucky the character you find is none of the needle characters, and then you'll process the string much faster)
< 1610356022 183621 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Well, according to this book, Boyer-Moore is slower and more complicated than its Horspool simplification.
< 1610356035 520362 :int-e!~noone@int-e.eu PRIVMSG #esoteric :I've never even heard of that one
< 1610356063 733199 :int-e!~noone@int-e.eu PRIVMSG #esoteric :But that's consistent with what I said :)
< 1610356074 411789 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :It's what GNU memmem uses, apparently.
< 1610356094 485010 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :(For sizes [3,256].)
< 1610356118 610053 :int-e!~noone@int-e.eu PRIVMSG #esoteric :(consistent: the difference is in the details that I never studied)
< 1610356224 960194 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Shift-And looks really simple.
< 1610357318 893525 :imode!~imode@unaffiliated/imode QUIT :Ping timeout: 260 seconds
< 1610357320 299574 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :This algorithm is just simulating an NFA in parallel with bitwise operations.
< 1610357337 372810 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :So the transition is: state = ((state << 1) | 1) & table[c];
< 1610357402 47546 :imode!~imode@unaffiliated/imode JOIN :#esoteric
< 1610357877 125352 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :And to be slightly trickier you can invert all the bits to get shift-or.
< 1610357895 245654 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Then shifting left gives you a 0 for free, so the transition is just: state = (state << 1) | table[c];
< 1610358088 281567 :LKoen!~LKoen@152.172.9.109.rev.sfr.net QUIT :Remote host closed the connection
< 1610359408 907128 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Hmm, maybe Horspool is just what I thought Boyer-Moore was.
< 1610359851 577934 :int-e!~noone@int-e.eu PRIVMSG #esoteric :If it's a simplification...
< 1610359864 352701 :int-e!~noone@int-e.eu PRIVMSG #esoteric :...it's likely to get taught.
< 1610359934 862810 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :If that's true, why does anyone teach bubble sort ever?
< 1610359943 591672 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :What a terrible algorithm.
< 1610360148 955868 :int-e!~noone@int-e.eu PRIVMSG #esoteric :Because of the name...
< 1610360164 980682 :int-e!~noone@int-e.eu PRIVMSG #esoteric :And it's so easy to implement in place.
< 1610360172 253546 :int-e!~noone@int-e.eu PRIVMSG #esoteric :And yes, ugly.
< 1610360183 81862 :int-e!~noone@int-e.eu PRIVMSG #esoteric :Also it's really a family of algorithms.
< 1610360345 170762 :int-e!~noone@int-e.eu PRIVMSG #esoteric :https://en.wikipedia.org/wiki/Sorting_network#Insertion_and_Bubble_networks
< 1610360411 763103 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Yes, I know it's the same sorting network as insertion sort.
< 1610360422 582783 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :But that's not an advantage over insertion sort. Insertion sort is just better.
< 1610360455 996531 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :It's not just more efficient, it's simpler and more obviously correct.
< 1610360474 743385 :int-e!~noone@int-e.eu PRIVMSG #esoteric :I really think it's the evocative name, and the physical analogy, that makes bubble sort popular.
< 1610360694 197191 :int-e!~noone@int-e.eu PRIVMSG #esoteric :from a practical perspective I'd probably start with bucket or radix sort on a deck of cards :P
< 1610360705 474003 :int-e!~noone@int-e.eu PRIVMSG #esoteric :"practical"
< 1610361033 486668 :rain1!~My_user_n@unaffiliated/rain1 JOIN :#esoteric
< 1610362281 91102 :LKoen!~LKoen@152.172.9.109.rev.sfr.net JOIN :#esoteric
< 1610362854 734125 :sftp!~sftp@unaffiliated/sftp QUIT :Excess Flood
< 1610362886 207192 :sftp!~sftp@unaffiliated/sftp JOIN :#esoteric
< 1610363665 271486 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Oh, this Horspool thing is actually not what I was thinking.
< 1610363697 196787 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :It places a window at a particular location, but then it just checks whether the window matches, which you can do either backward or forward.
< 1610363714 202007 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Then if there's a mismatch it decides how to move the window based on the last byte in the window. That's it.
> 1610363807 658225 PRIVMSG #esoteric :14[[07Special:Log/newusers14]]4 create10 02 5* 03Txlyre 5*  10New user account
> 1610365143 748062 PRIVMSG #esoteric :14[[07Esolang:Introduce yourself14]]4 10 02https://esolangs.org/w/index.php?diff=79931&oldid=79926 5* 03Txlyre 5* (+161) 10Add my introduction.
< 1610367397 458679 :imode!~imode@unaffiliated/imode QUIT :Quit: WeeChat 3.0
> 1610368747 496411 PRIVMSG #esoteric :14[[07Length14]]4 10 02https://esolangs.org/w/index.php?diff=79932&oldid=79812 5* 03Nailuj29 5* (+99) 10add C# compiler
< 1610369128 999485 :txlyre!~papope@89.113.127.197 JOIN :#esoteric
< 1610369927 273944 :LKoen!~LKoen@152.172.9.109.rev.sfr.net QUIT :Quit: “It’s only logical. First you learn to talk, then you learn to think. Too bad it’s not the other way round.”
< 1610370215 33169 :txlyre!~papope@89.113.127.197 QUIT :Quit: -a- IRC for Android 2.1.59
< 1610370937 754406 :xelxebar_!~xelxebar@gateway/tor-sasl/xelxebar JOIN :#esoteric
< 1610370983 776710 :xelxebar!~xelxebar@gateway/tor-sasl/xelxebar QUIT :Ping timeout: 240 seconds
< 1610371636 439668 :heroux!sandroco@gateway/shell/insomnia247/x-ntofnzsnzxymfmks QUIT :Ping timeout: 240 seconds
< 1610371683 359602 :user3456!user3456@gateway/shell/insomnia247/x-lckblyjpdyzydjwo QUIT :Ping timeout: 258 seconds
< 1610372030 511140 :user3456!user3456@gateway/shell/insomnia247/x-itwqtnpgiygiaaii JOIN :#esoteric
< 1610372047 396999 :heroux!sandroco@gateway/shell/insomnia247/x-mxtksflgdxdzuqsa JOIN :#esoteric
< 1610372660 797097 :LKoen!~LKoen@152.172.9.109.rev.sfr.net JOIN :#esoteric
< 1610372674 909956 :b_jonas!~a@catv-176-63-12-89.catv.broadband.hu PRIVMSG #esoteric :shachaf: yes. it's an algorithm that almost never comes up anymore on modern machines. it made a bit more sense back when RAMs read one byte at a time but were the same frequency as the CPU and almost no latency. you'll find a more precise description in Knuth volume 5. it isn't even described in Cormen, or in Rónyai–Ivanyos–Szabó, ... hmm
< 1610372719 827319 :b_jonas!~a@catv-176-63-12-89.catv.broadband.hu PRIVMSG #esoteric :it must be in some book. I know I was supposed to understand this (and the other two string search algorithms) for an exam. 
< 1610372960 835034 :b_jonas!~a@catv-176-63-12-89.catv.broadband.hu PRIVMSG #esoteric :I don't think it's in ed. Iványi either
< 1610373134 796879 :b_jonas!~a@catv-176-63-12-89.catv.broadband.hu PRIVMSG #esoteric :wait...
< 1610373205 316029 :b_jonas!~a@catv-176-63-12-89.catv.broadband.hu PRIVMSG #esoteric :is Boyer-Moore the same as that algorithm?
< 1610373254 581009 :b_jonas!~a@catv-176-63-12-89.catv.broadband.hu PRIVMSG #esoteric :I'm confused
< 1610373316 543619 :b_jonas!~a@catv-176-63-12-89.catv.broadband.hu PRIVMSG #esoteric :https://regi.tankonyvtar.hu/hu/tartalom/tamop425/0046_algoritmusok/ch11.html this book lists three different nontrivial string search algorithms
< 1610373332 483096 :b_jonas!~a@catv-176-63-12-89.catv.broadband.hu PRIVMSG #esoteric :but maybe there are four?
< 1610373956 482427 :adu!~arobbins@c-76-111-99-194.hsd1.md.comcast.net JOIN :#esoteric
< 1610374057 602243 :adu!~arobbins@c-76-111-99-194.hsd1.md.comcast.net QUIT :Client Quit
< 1610374247 505223 :arseniiv!~arseniiv@145.255.10.228 JOIN :#esoteric
< 1610374258 904414 :Arcorann!~awych@159-196-65-46.9fc441.mel.nbn.aussiebb.net QUIT :Ping timeout: 260 seconds
< 1610376093 611715 :mmmattyx!uid17782@gateway/web/irccloud.com/x-wzxcapgnieyfthce JOIN :#esoteric
< 1610376967 936569 :ArthurStrong!~ArthurStr@188.163.100.177 JOIN :#esoteric
< 1610377249 425785 :Sgeo!~Sgeo@ool-18b98aa4.dyn.optonline.net JOIN :#esoteric
< 1610377790 230002 :LKoen!~LKoen@152.172.9.109.rev.sfr.net QUIT :Remote host closed the connection
< 1610379106 989099 :LKoen!~LKoen@152.172.9.109.rev.sfr.net JOIN :#esoteric
> 1610379592 259318 PRIVMSG #esoteric :14[[07Special:Log/newusers14]]4 create10 02 5* 03Shahryar 5*  10New user account
> 1610380047 58899 PRIVMSG #esoteric :14[[07Esolang:Introduce yourself14]]4 10 02https://esolangs.org/w/index.php?diff=79933&oldid=79931 5* 03Shahryar 5* (+325) 10/* Introductions */
> 1610380634 26286 PRIVMSG #esoteric :14[[07Language list14]]4 10 02https://esolangs.org/w/index.php?diff=79934&oldid=79904 5* 03Shahryar 5* (+16) 10/* Non-alphabetic */
> 1610380753 858006 PRIVMSG #esoteric :14[[07Language list14]]4 10 02https://esolangs.org/w/index.php?diff=79935&oldid=79934 5* 03Shahryar 5* (+16) 10/* P */
> 1610381554 912352 PRIVMSG #esoteric :14[[07Plutonium14]]4 N10 02https://esolangs.org/w/index.php?oldid=79936 5* 03Shahryar 5* (+408) 10Plutonium Programming Language Intro
> 1610381799 646031 PRIVMSG #esoteric :14[[07User:Shahryar14]]4 N10 02https://esolangs.org/w/index.php?oldid=79937 5* 03Shahryar 5* (+194) 10Created page with "Hi, I am Shahryar Ahmad.I am a self taught teenage programmer.I love programming.I created my own programming language plutonium.I code in C/C++ and these are my favourite pro..."
> 1610382653 712522 PRIVMSG #esoteric :14[[07Length14]]4 10 02https://esolangs.org/w/index.php?diff=79938&oldid=79932 5* 03Nailuj29 5* (+72) 10
> 1610383316 371772 PRIVMSG #esoteric :14[[07Length14]]4 10 02https://esolangs.org/w/index.php?diff=79939&oldid=79938 5* 03Nailuj29 5* (-4) 10
> 1610383684 319418 PRIVMSG #esoteric :14[[07Length14]]4 10 02https://esolangs.org/w/index.php?diff=79940&oldid=79939 5* 03Nailuj29 5* (+83) 10
< 1610384091 129918 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :b_jonas: The algorithm I'm describing is certainly in the Boyer-Moore family.
< 1610384169 269162 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :The book I'm reading divides string-in-string search algorithms into approximately three families, KMP-like, BM-like, and ones based on substrings (which it calls factors).
< 1610384195 33720 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Rabin-Karp is yet another method, which it hasn't even mentioned yet.
< 1610384217 786966 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Maybe it'll mention it if don't-care characters come up later.
< 1610384271 435583 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Anyway, BNDM -- Backward Nondeterministic Dawg Matching -- is an example of the factor algorithm. https://www-igm.univ-mlv.fr/~lecroq/string/bndm.html looks like a link for it?
< 1610384425 897800 :xelxebar_!~xelxebar@gateway/tor-sasl/xelxebar QUIT :Remote host closed the connection
< 1610384449 720306 :xelxebar!~xelxebar@gateway/tor-sasl/xelxebar JOIN :#esoteric
< 1610384453 801672 :b_jonas!~a@catv-176-63-12-89.catv.broadband.hu PRIVMSG #esoteric :shachaf: Rabin-Karp is mentioned in the book that I linked, and in Cormen
< 1610384471 288578 :b_jonas!~a@catv-176-63-12-89.catv.broadband.hu PRIVMSG #esoteric :shachaf: isn't there an additional family of randomized (hashing) algorithms?
< 1610384478 36756 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Yes, I know what Rabin-Karp is, I just mean that so far it hasn't mentioned rolling hashes or anything.
< 1610384510 76687 :b_jonas!~a@catv-176-63-12-89.catv.broadband.hu PRIVMSG #esoteric :ah right, Rabin-Karp is the randomized one
< 1610384533 830026 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :My vague recollection of this topic is that optimal time for searching with don't-care characters in the pattern is pretty tricky to achieve with conventional algorithms.
< 1610384560 518744 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :And that maybe a rolling hash method does best at it, or something.
< 1610384620 896326 :b_jonas!~a@catv-176-63-12-89.catv.broadband.hu PRIVMSG #esoteric :shachaf: isn't that only if you insist on theoretical asymptotics though, while most of the practical input data that you want to search for is much easier, though you have to be careful when users can give you text and/or search queries of course?
< 1610384642 3127 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :I think that's right. This book is pretty practically-minded.
< 1610384689 820433 :b_jonas!~a@catv-176-63-12-89.catv.broadband.hu PRIVMSG #esoteric :well, in the end we'll just have to wait for Knuth vol 5 for a clear summary and final word
< 1610384797 22474 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :I quite like these methods that store a set of states in a machine word.
< 1610384826 177563 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Even if they're limited to search for patterns of size 64 or something.
< 1610384938 955807 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :One thing this book doesn't cover at all is offline algorithms, where you can build an index on the text.
< 1610384960 649943 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :I'd read another book about those because there are so many interesting tricks there.
< 1610385515 594480 :sprocklem!~sprocklem@unaffiliated/sprocklem JOIN :#esoteric
> 1610385658 960512 PRIVMSG #esoteric :14[[07Special:Log/newusers14]]4 create10 02 5* 03Chibiningen 5*  10New user account
> 1610385859 453574 PRIVMSG #esoteric :14[[07Esolang:Introduce yourself14]]4 10 02https://esolangs.org/w/index.php?diff=79941&oldid=79933 5* 03Chibiningen 5* (+159) 10
> 1610385921 518138 PRIVMSG #esoteric :14[[07User:Chibiningen14]]4 N10 02https://esolangs.org/w/index.php?oldid=79942 5* 03Chibiningen 5* (+13) 10Created page with "Irashaimasen."
> 1610386089 185674 PRIVMSG #esoteric :14[[07Talk:Imaginary function14]]4 10 02https://esolangs.org/w/index.php?diff=79943&oldid=43070 5* 03Chibiningen 5* (+164) 10
< 1610386264 329854 :mmmattyx!uid17782@gateway/web/irccloud.com/x-wzxcapgnieyfthce QUIT :Quit: Connection closed for inactivity
< 1610387294 436689 :delta23!~deltaepsi@d179-68-39-184.evv.wideopenwest.com JOIN :#esoteric
< 1610389183 6957 :privateger!privateger@gateway/vpn/mullvad/privateger JOIN :#esoteric
> 1610390035 651283 PRIVMSG #esoteric :14[[07V14]]4 M10 02https://esolangs.org/w/index.php?diff=79944&oldid=79887 5* 03Bo Tie 5* (+0) 10oops
< 1610390084 784611 :FreeFull!~freefull@defocus/sausage-lover JOIN :#esoteric
> 1610390195 426699 PRIVMSG #esoteric :14[[07V14]]4 M10 02https://esolangs.org/w/index.php?diff=79945&oldid=79944 5* 03Bo Tie 5* (+0) 10oops again
< 1610391632 443316 :Lord_of_Life_!~Lord@unaffiliated/lord-of-life/x-0885362 JOIN :#esoteric
< 1610391757 548187 :Lord_of_Life!~Lord@unaffiliated/lord-of-life/x-0885362 QUIT :Ping timeout: 264 seconds
< 1610391802 855383 :Lord_of_Life_!~Lord@unaffiliated/lord-of-life/x-0885362 NICK :Lord_of_Life
< 1610392260 373195 :delta23!~deltaepsi@d179-68-39-184.evv.wideopenwest.com QUIT :Remote host closed the connection
< 1610392290 323465 :delta23!~deltaepsi@d179-68-39-184.evv.wideopenwest.com JOIN :#esoteric
< 1610392293 141083 :delta23!~deltaepsi@d179-68-39-184.evv.wideopenwest.com QUIT :Read error: Connection reset by peer
< 1610392334 498475 :delta23!~deltaepsi@d179-68-39-184.evv.wideopenwest.com JOIN :#esoteric
< 1610394404 61252 :jess!jess@freenode/staff/jess JOIN :#esoteric
< 1610394460 180211 :jess!jess@freenode/staff/jess QUIT :Client Quit
< 1610394495 226458 :jess!jess@freenode/staff/jess JOIN :#esoteric
< 1610394746 328262 :rain1!~My_user_n@unaffiliated/rain1 PRIVMSG #esoteric :file format for packing multiple files togethr:  (filename\0data\0)*  works with files who do not contain \0
< 1610394910 221053 :MDude!~MDude@71.50.47.112 JOIN :#esoteric
< 1610394944 436518 :also_uplime!nchambers@learnprogramming/staff/nchambers QUIT :Disconnected by services
< 1610394957 831294 :also_uplime!nchambers@learnprogramming/staff/nchambers JOIN :#esoteric
< 1610395051 517951 :zzo38!~zzo38@host-24-207-14-22.public.eastlink.ca PRIVMSG #esoteric :Yes, although other than text files, many files will contain \0
< 1610395100 539199 :kmc!~beehive@unaffiliated/kmcallister PRIVMSG #esoteric :https://en.wikipedia.org/wiki/Consistent_Overhead_Byte_Stuffing
< 1610395394 100624 :zzo38!~zzo38@host-24-207-14-22.public.eastlink.ca PRIVMSG #esoteric :That will work, although that makes it a more complicated format. (Although for some applications that might still be helpful, I suppose.)
< 1610395405 237900 :kmc!~beehive@unaffiliated/kmcallister PRIVMSG #esoteric :yeah
< 1610395768 937041 :zzo38!~zzo38@host-24-207-14-22.public.eastlink.ca PRIVMSG #esoteric :Although I generally prefer the Hamster archive format, which is like what rain1 described except instead of adding a null byte after the data, add the 32-bit PDP-endian data size before the data. (Of course, different formats have their own advantages and disadvantages, such as this won't work if the data size won't fit in a 32-bit number.)
< 1610395774 232821 :kmc!~beehive@unaffiliated/kmcallister PRIVMSG #esoteric :if the goal is just to pack files together then i reckon a length-prefixed format is better than a delimited format
< 1610395777 241096 :kmc!~beehive@unaffiliated/kmcallister PRIVMSG #esoteric :yeah
< 1610395818 775721 :zzo38!~zzo38@host-24-207-14-22.public.eastlink.ca PRIVMSG #esoteric :Yes, I think so too.
< 1610395822 195460 :kmc!~beehive@unaffiliated/kmcallister PRIVMSG #esoteric :the length-prefixed format doesn't require processing the file data at all, and it allows a reader to easily skip files that are not of interest, assuming the archive is on a seekable medium
< 1610395934 576262 :zzo38!~zzo38@host-24-207-14-22.public.eastlink.ca PRIVMSG #esoteric :Yes, I did think of that too (and have taken advantage of that too).
< 1610396074 655322 :kmc!~beehive@unaffiliated/kmcallister PRIVMSG #esoteric :COBS is good for something like a serial data link where a) you don't necessarily know the length of a packet when you start transmitting it and b) you want to be able to jump into the middle of a stream and resynchronize as soon as you reach the end of a packet
< 1610396119 273952 :kmc!~beehive@unaffiliated/kmcallister PRIVMSG #esoteric :I am thinking the next time I build an embedded system which needs to send structured data over a serial link, I might use CBOR + COBS
< 1610396273 384955 :zzo38!~zzo38@host-24-207-14-22.public.eastlink.ca PRIVMSG #esoteric :Yes, I believe you; that makes sense.
< 1610396596 605419 :kmc!~beehive@unaffiliated/kmcallister PRIVMSG #esoteric :serialization is a surprisingly hard problem
< 1610396628 228829 :kmc!~beehive@unaffiliated/kmcallister PRIVMSG #esoteric :it often seems stupid that the world has so many serialization formats, but it's surprisingly tricky to design a good one, and there are a lot of conflicting requirements such that there isn't necessarily one best choice
< 1610397109 586006 :Hooloovo0!Hooloovoo@sorunome.de PRIVMSG #esoteric :yeah. that's for sure. 
< 1610398385 143363 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Man, this string searching loop is so good: for (int i = 0; i < text_size; i++) { state = (state >> 1) | table[text[i]]; if ((state & 1) == 0) { /* found */ } }
< 1610398529 754063 :rain1!~My_user_n@unaffiliated/rain1 PRIVMSG #esoteric :does table just put how many chars left are need as bits?
< 1610398605 804513 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :I guess you can put it that way?
< 1610398617 410053 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Each bit is an NFA state.
< 1610398663 981079 :rain1!~My_user_n@unaffiliated/rain1 PRIVMSG #esoteric :it seems ok, very basic no skip aheads
< 1610398725 610359 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Yes, it's only for small patterns.
< 1610398845 112018 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :If you want skipahead, Horspool is also really simple (way simpler than Boyer-Moore) and good.
< 1610398958 932872 :zzo38!~zzo38@host-24-207-14-22.public.eastlink.ca PRIVMSG #esoteric :kmc: I think that different formats can be good for different purposes, although it is true there are some problem with some of them
< 1610398959 621262 :rain1!~My_user_n@unaffiliated/rain1 PRIVMSG #esoteric :thanks i didn't know about it
< 1610398985 461652 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :window_left := 0; while (window_left <= end - pattern_size) { if (s[window_left:window_left+pattern_size] == pattern) { /* found */ } else { window_left += table[text[window_left + pattern_size - 1]]; }
< 1610398994 65495 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Where that if is doing string comparison, of course.
< 1610399055 261312 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :And the table just has the rightmost occurrence of each character (excluding the last one).
< 1610399214 777724 :zzo38!~zzo38@host-24-207-14-22.public.eastlink.ca PRIVMSG #esoteric :I think XML is too often used as a general purpose serialization format when it isn't very good for that; what XML is good for is stuff like HTML (and avoids some of the problems of HTML).
< 1610399236 942833 :kmc!~beehive@unaffiliated/kmcallister PRIVMSG #esoteric :XML has a lot of problems
< 1610399286 253525 :zzo38!~zzo38@host-24-207-14-22.public.eastlink.ca PRIVMSG #esoteric :Yes, it does have a lot of its own problems too
< 1610399777 7157 :zzo38!~zzo38@host-24-207-14-22.public.eastlink.ca PRIVMSG #esoteric :One serialization format that is often missed is the format produced by the printobject operator in PostScript.
< 1610399786 926668 :kmc!~beehive@unaffiliated/kmcallister PRIVMSG #esoteric :I do like some things that XML can do, such as namespacing of tags, ability to embed one type of XML document in another, and schemas to check validity
< 1610399792 392980 :kmc!~beehive@unaffiliated/kmcallister PRIVMSG #esoteric :but these things are often not used or used improperly
< 1610399797 345878 :kmc!~beehive@unaffiliated/kmcallister PRIVMSG #esoteric :and the concrete syntax of XML is very cumbersome
< 1610399808 908610 :kmc!~beehive@unaffiliated/kmcallister PRIVMSG #esoteric :which defeats the purpose of a "human-readable" format
< 1610399823 796701 :kmc!~beehive@unaffiliated/kmcallister PRIVMSG #esoteric :and if it's not going to be human-readable/editable then it could be a more efficient and easy to parse binary format
< 1610399839 379627 :kmc!~beehive@unaffiliated/kmcallister PRIVMSG #esoteric :zzo38: what is that format?
< 1610399863 975309 :zzo38!~zzo38@host-24-207-14-22.public.eastlink.ca PRIVMSG #esoteric :XML is way too often misused I think. The good things XML can do is good for things like HTML, not for other kind of stuff, I think.
< 1610399894 605751 :zzo38!~zzo38@host-24-207-14-22.public.eastlink.ca PRIVMSG #esoteric :kmc: Here is a description: http://fileformats.archiveteam.org/wiki/PostScript_binary_object_format
> 1610399937 626357 PRIVMSG #esoteric :14[[07Plutonium14]]4 M10 02https://esolangs.org/w/index.php?diff=79946&oldid=79936 5* 03Tetrapyronia 5* (+53) 10added link (needs formatting and stuff)
> 1610399964 553819 PRIVMSG #esoteric :14[[07Plutonium14]]4 M10 02https://esolangs.org/w/index.php?diff=79947&oldid=79946 5* 03Tetrapyronia 5* (-9) 10
< 1610400192 19942 :kmc!~beehive@unaffiliated/kmcallister PRIVMSG #esoteric :HTML isn't even proper XML
< 1610400204 630853 :kmc!~beehive@unaffiliated/kmcallister PRIVMSG #esoteric :and the project to turn it into proper XML failed and was abandoned
< 1610400254 526678 :zzo38!~zzo38@host-24-207-14-22.public.eastlink.ca PRIVMSG #esoteric :Yes, I know, HTML isn't even proper XML.
< 1610400265 640902 :b_jonas!~a@catv-176-63-12-89.catv.broadband.hu PRIVMSG #esoteric :kmc: it wasn't abandonned. while we don't transmit HTML written as XML, browsers and their Javascript DOM interface effectively expose a view of the live internal state of HTML document that is basically an XML tree
< 1610400298 175053 :b_jonas!~a@catv-176-63-12-89.catv.broadband.hu PRIVMSG #esoteric :so XML is a good way to describe how the semantics works
< 1610400348 883912 :kmc!~beehive@unaffiliated/kmcallister PRIVMSG #esoteric :it still differs from XML
< 1610400354 584576 :b_jonas!~a@catv-176-63-12-89.catv.broadband.hu PRIVMSG #esoteric :we just don't want to apply the restrictions of XML to the HTML files that we transmit because that'd be pointless. like, no \x00 characters? it'd just be a stupid extra requirement on the side that serves the XHTML, when the browser side will always have to be able to parse full HTML anyway.
< 1610400391 254919 :b_jonas!~a@catv-176-63-12-89.catv.broadband.hu PRIVMSG #esoteric :kmc: sure, it differs, but I don't think that counts as abandonned
< 1610400394 611657 :kmc!~beehive@unaffiliated/kmcallister PRIVMSG #esoteric :I agree that HTML is similar to XML and some of the same concepts apply when working with a DOM
< 1610400401 221933 :b_jonas!~a@catv-176-63-12-89.catv.broadband.hu PRIVMSG #esoteric :the XML thing wasn't a dead-end
< 1610400409 861919 :b_jonas!~a@catv-176-63-12-89.catv.broadband.hu PRIVMSG #esoteric :it just led to the DOM interface that isn't quite XML
< 1610400422 51251 :kmc!~beehive@unaffiliated/kmcallister PRIVMSG #esoteric :the idea of serializing HTML pages in an XML compatible format basically went nowhere
< 1610400432 426893 :kmc!~beehive@unaffiliated/kmcallister PRIVMSG #esoteric :there is actually an XML compatible serialization of HTML5 documents (XHTML5)
< 1610400435 545881 :kmc!~beehive@unaffiliated/kmcallister PRIVMSG #esoteric :but I don't think it's used much
< 1610400442 489236 :kmc!~beehive@unaffiliated/kmcallister PRIVMSG #esoteric :it does not parse as standard HTML5, I don't think
< 1610400447 237229 :kmc!~beehive@unaffiliated/kmcallister PRIVMSG #esoteric :it would have a different content-type
< 1610400451 130310 :kmc!~beehive@unaffiliated/kmcallister PRIVMSG #esoteric :and a different, much stricter parser
< 1610400482 359615 :kmc!~beehive@unaffiliated/kmcallister PRIVMSG #esoteric :versus the HTML5 parser which is a precisely specified complicated ball of garbage meant to parse any vaguely correct HTML-ish thing anyone's ever written since 1990
< 1610400743 201901 :fizzie!fis@unaffiliated/fizzie PRIVMSG #esoteric :"-//W3C//DTD XHTML 1.0 Transitional//EN" for life
< 1610400814 877183 :kmc!~beehive@unaffiliated/kmcallister PRIVMSG #esoteric :<!DOCTYPE html> is so much shorter
< 1610400819 762708 :fizzie!fis@unaffiliated/fizzie PRIVMSG #esoteric :Remember when web pages had that button at the bottom where it proudly proclaimed which standard it validates at, and when you clicked it, you got a validator report with at least a dozen errors? 
< 1610400827 385758 :kmc!~beehive@unaffiliated/kmcallister PRIVMSG #esoteric :yup
< 1610401352 433574 :user24!~user24@2a02:810a:1440:7304:85f0:b68e:f6b2:3799 JOIN :#esoteric
< 1610403174 646103 :user24!~user24@2a02:810a:1440:7304:85f0:b68e:f6b2:3799 QUIT :Quit: Leaving
< 1610403397 445076 :privateger!privateger@gateway/vpn/mullvad/privateger QUIT :Quit: Leaving.
< 1610403817 487041 :arseniiv_!~arseniiv@145.255.10.228 JOIN :#esoteric
< 1610403898 527701 :arseniiv!~arseniiv@145.255.10.228 QUIT :Ping timeout: 246 seconds
< 1610405215 677162 :oren!~oren@ec2-34-239-129-109.compute-1.amazonaws.com PRIVMSG #esoteric :Did they ever fix the vertical alignment problem in HTML?
< 1610405238 274113 :oren!~oren@ec2-34-239-129-109.compute-1.amazonaws.com PRIVMSG #esoteric :(where there is no portable way to vertically centre anything, other than using tables)
< 1610405277 938770 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Does flex-whatever not do it nowadays?
< 1610405309 841497 :zzo38!~zzo38@host-24-207-14-22.public.eastlink.ca PRIVMSG #esoteric :Isn't there some CSS command to position something as though it is a table cell?
< 1610405402 969103 :zzo38!~zzo38@host-24-207-14-22.public.eastlink.ca PRIVMSG #esoteric :(Although maybe I am wrong; my use of CSS is mostly limited to correcting the bad designs of other CSS writers.)
< 1610405489 364194 :oren!~oren@ec2-34-239-129-109.compute-1.amazonaws.com PRIVMSG #esoteric :oh apparently display:flex with align-items:center does vertical centring
< 1610405627 708891 :delta23!~deltaepsi@d179-68-39-184.evv.wideopenwest.com QUIT :Quit: Leaving
< 1610406512 343835 :FreeFull!~freefull@defocus/sausage-lover QUIT :Read error: Connection reset by peer
< 1610406513 368580 :LKoen!~LKoen@152.172.9.109.rev.sfr.net QUIT :Quit: “It’s only logical. First you learn to talk, then you learn to think. Too bad it’s not the other way round.”
< 1610407326 590048 :rain1!~My_user_n@unaffiliated/rain1 QUIT :Quit: WeeChat 3.0
< 1610407545 493488 :FreeFull!~freefull@defocus/sausage-lover JOIN :#esoteric
< 1610408265 852790 :fizzie!fis@unaffiliated/fizzie PRIVMSG #esoteric :They did a multicolumn CSS thing too, right? 
< 1610408864 557017 :ArthurStrong!~ArthurStr@188.163.100.177 QUIT :Quit: leaving
< 1610409262 851338 :kmc!~beehive@unaffiliated/kmcallister PRIVMSG #esoteric :zzo38: yes, table layout is fully specified by CSS
< 1610409297 399679 :kmc!~beehive@unaffiliated/kmcallister PRIVMSG #esoteric :that is, there is nothing special about <table> and <td> etc. tags, you could use <div class="table"> and <div class="td"> and so forth and get the same results with an appropriate stylesheet
< 1610409326 578880 :kmc!~beehive@unaffiliated/kmcallister PRIVMSG #esoteric :fun fact: you can even style normally invisible tags such as <script> to be visible
< 1610409339 704507 :kmc!~beehive@unaffiliated/kmcallister PRIVMSG #esoteric :try injecting "script { display: block; }" as user CSS on your favorite website and see what happens
< 1610409347 573194 :kmc!~beehive@unaffiliated/kmcallister PRIVMSG #esoteric :talk about literate programming!
< 1610409428 450263 :zzo38!~zzo38@host-24-207-14-22.public.eastlink.ca PRIVMSG #esoteric :Yes, although <TABLE> is still useful for some purposes, such as, if the user disabled CSS, if you use a browser that doesn't have CSS, or so that a browser that implements some special commands for use with tables can deal with tables, such as sorting, SQL queries, export, etc.
< 1610409563 510032 :kmc!~beehive@unaffiliated/kmcallister PRIVMSG #esoteric :yeah
< 1610409589 41013 :kmc!~beehive@unaffiliated/kmcallister PRIVMSG #esoteric :as far as i know, the use of <table> is still considered correct for things that are actually semantically tables
< 1610409594 507428 :kmc!~beehive@unaffiliated/kmcallister PRIVMSG #esoteric :just not for random bits of site layout