From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=DKIM_INVALID,DKIM_SIGNED, HTML_MESSAGE,MAILING_LIST_MULTI,MIME_HTML_ONLY,MIME_HTML_ONLY_MULTI, MIME_QP_LONG_LINE,MPART_ALT_DIFF autolearn=ham autolearn_force=no version=3.4.4 Received: (qmail 28812 invoked from network); 2 Mar 2023 05:17:20 -0000 Received: from minnie.tuhs.org (50.116.15.146) by inbox.vuxu.org with ESMTPUTF8; 2 Mar 2023 05:17:20 -0000 Received: from minnie.tuhs.org (localhost [IPv6:::1]) by minnie.tuhs.org (Postfix) with ESMTP id 1D8CE434B7; Thu, 2 Mar 2023 15:17:16 +1000 (AEST) Received: from pb-smtp21.pobox.com (pb-smtp21.pobox.com [173.228.157.53]) by minnie.tuhs.org (Postfix) with ESMTPS id 48247434B3 for ; Thu, 2 Mar 2023 15:17:11 +1000 (AEST) Received: from pb-smtp21.pobox.com (unknown [127.0.0.1]) by pb-smtp21.pobox.com (Postfix) with ESMTP id D72EC1DAAD3; Thu, 2 Mar 2023 00:17:10 -0500 (EST) (envelope-from davida@pobox.com) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed; d=pobox.com; h= content-type:content-transfer-encoding:from:mime-version:subject :date:message-id:references:cc:in-reply-to:to; s=sasl; bh=h3gdJY MGwAaW4bIQm5mVIL7TXzI3fddIZjeZpRRZX0Y=; b=acVlIVIX4yfeXrttl7ZwTw AS5JRQqRFJUQuvQjRBhS8lvop4902EJ2Qd+wGjRDGFYGpuSKxriVnFHYb1OHycd9 i6m1QdKGpM6XGJ+M+oK//nPZiohcEEjbmPxYzl8y+5F/F1R/COFDHdNijAYmLjGv RX38MEcraK13FaBZWAFlY= Received: from pb-smtp21.sea.icgroup.com (unknown [127.0.0.1]) by pb-smtp21.pobox.com (Postfix) with ESMTP id D00121DAAD1; Thu, 2 Mar 2023 00:17:10 -0500 (EST) (envelope-from davida@pobox.com) Received: from smtpclient.apple (unknown [203.132.93.11]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by pb-smtp21.pobox.com (Postfix) with ESMTPSA id 0FBAB1DAAD0; Thu, 2 Mar 2023 00:17:08 -0500 (EST) (envelope-from davida@pobox.com) Content-Type: multipart/alternative; boundary=Apple-Mail-FC42B416-9EFB-46F1-9736-D5AACBBF9CCC Content-Transfer-Encoding: 7bit From: David Arnold Mime-Version: 1.0 (1.0) Date: Thu, 2 Mar 2023 16:16:53 +1100 Message-Id: References: In-Reply-To: To: Douglas McIlroy X-Mailer: iPhone Mail (20C65) X-Pobox-Relay-ID: 7A6D5700-B8B9-11ED-8F59-B31D44D1D7AA-29049682!pb-smtp21.pobox.com Message-ID-Hash: ZNQOJ4ZEA2WHQ2X3ONOKV7WFA5MSH3AM X-Message-ID-Hash: ZNQOJ4ZEA2WHQ2X3ONOKV7WFA5MSH3AM X-MailFrom: davida@pobox.com X-Mailman-Rule-Misses: dmarc-mitigation; no-senders; approved; emergency; loop; banned-address; member-moderation; nonmember-moderation; administrivia; implicit-dest; max-recipients; max-size; news-moderation; no-subject; digests; suspicious-header CC: The Eunuchs Hysterical Society X-Mailman-Version: 3.3.6b1 Precedence: list Subject: [TUHS] Re: A second Unix Patent List-Id: The Unix Heritage Society mailing list Archived-At: List-Archive: List-Help: List-Owner: List-Post: List-Subscribe: List-Unsubscribe: --Apple-Mail-FC42B416-9EFB-46F1-9736-D5AACBBF9CCC Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: quoted-printable This one, perhaps:

https://patents.google.com/patent/US3964059A/en<= /div>




d
<= div dir=3D"ltr">


On 2 Mar 2023, at 15:41, Douglas McIlroy <douglas.mcil= roy@dartmouth.edu> wrote:

=EF=BB=BF
Typo, in v3 through v6, may b= e the most creative Unix program to have come out of Bell Labs. It served as= a spell checker before spell(1), though it knew nothing about spelling beyo= nd a list of the most common words in the language. This brainchild of Bob M= orris would, in his words, work just as well in Urdu as in English.

T= he beautiful trick: gather trigram frequencies in the document, then print o= ut a list of the individual words in increasing order of the likelihood that= they came from the statistical source that those frequencies  characterize. Typos (as distinct from phonetic misspellings) generally float= ed toward the beginning of the list and so were easy to spot.

But tha= t's not all that Bob invented. 26^3 16-bit trigram counts didn't fit in the P= DP-11 memory, so he counted them in 8-bit bytes. To do so he invented the tr= ick of "counting large integers in small registers". Roughly speaking, when y= ou see a word whose current count is in the range 2^(n-1) to 2^n-1, you incr= ement the count with probability 1/2^n, thus getting an approximation to lg n= , which serves in estimating the entropy of each word.

This counting m= ethod merited a patent and is now recognized as the first of what is now an a= ctive subfield of theoretical computer science--memory-bounded streaming alg= orithms.

Doug

On Wed, Mar 1, 2023 at 6:00=E2=80=AFPM Warner Losh &l= t;imp@bsdimp.com> wrote:
<= blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-le= ft:1px solid rgb(204,204,204);padding-left:1ex">
In looking a= t the first AUUGN today, I noticed the following at the end of a letter John= Lions sent home when he spent a sabbatical at Bell Labs

=
<image.png>

I've seen the first patent, but n= ot the second one... That's got to be a joke or inside joke, right? Anybody k= now anything else about it?
= --Apple-Mail-FC42B416-9EFB-46F1-9736-D5AACBBF9CCC--