HDTenEightyP/NetNews huggingface dataset:
From: rem@public.BTR.COM (Robert E. Maas  rem@btr.com)
Newsgroups: comp.compression
Subject: Re: digraph compression
Date: 26 Jul 92 20:51:21 GMT
Organization: BTR Public Access UNIX, MtnView CA. Contact: Customer Service cs@BTR.COM

<<I would like to compress a directed graph, but still be able to
determine whether one node points to another directly from the
compressed file. Any suggestions?>>

Before your question can be answered, a lot of ambiguities need to be
clarified: Do you have ONLY a set of nodes and directional links, or
are there labels on the nodes and/or the links? Are the labels strings
of text or numbers (integers)? Is there any other information
associated with the nodes or links? (I.e. is this a database with links
between various records, or just a mathematical graph with no
information content other than its structure?) If the nodes have no
labels whatsoever, not even numbers, how do you ask questions about
whether one node links to another or not? What sorts of questions about
links do you specifically need to answer efficiently? (Given x and y,
is there a link from x to y; Given x, what are all y such that there's
a link from x to y; Given y, what are all x such that there's a link
from x to y.) Depending on which kinds of questions you want to answer,
and what the labels on nodes are, various different kinds of hash
tables may be suitable for quickly looking up the answers to those
questions. How many nodes and links are there altogether in your
directed graph? What is the maximum number of characters in a label?
What is the average and maximum amount of data associated with any
node? Maybe if you have a mathematical graph with no labels and no
information content, maybe you just want a way to abstract a given
graph down to the minimum by which you can compare it to another, in
which case hashing the whole graph down to a single 32-bit number would
suffice. (But that doesn't sound like what you want here, right?)

If your graph has labels on nodes, and a large number of nodes, and
only a small fraction of possible links exist, and you want to answer
only YES/NO questions whether x->y is a link, a double-hashing on the
two keys with a simple yes/no answer would suffice. The most efficient
way storagewise to do this may be to have a bitmap which is by default
all zeroes but where each x->y link causes several different
pseudo-random bits to be turned to 1 based on the hash number that was
computed. Then to find if a given link appears you check ALL the bits
associated with that x->y link and if ALL are on then the link probably
exists while if not all are on then the link definitely doesn't exist.
If the graph is static, you can compile it once, then run a background
process that generates all possible x->y pairs to see if there are any
false matches, and collect a list of those exceptions. Then discard the
original data (but keep a backup somewhere of course) and use the
bitmap plus the exception list to answer all x->y YES/NO queries.
Xref: sparky comp.compression:2808 rec.video:9587 rec.video.satellite:3772 rec.video.production:1132
From: monta@image.mit.edu (Peter Monta)
Newsgroups: comp.compression,rec.video,rec.video.satellite,rec.video.production
Subject: Compression artifacts in NBC Olympic coverage
Date: 26 Jul 92 23:13:44 GMT
Organization: MIT Advanced Television Research Program

While I was watching the US-Angola basketball game and the coverage
of the early gymnastics compulsories, I thought I saw several image
artifacts.  Finally I taped a segment of the gymnastics and waited for
a particularly bad example, then went through it frame by frame.

There's no question about it:  there are block artifacts in the
regions where a fast-moving object occludes or reveals the background.
For example, NBC showed the compulsory floor exercise of Maria
Neculita (Romania) at around 5:30pm EDT.  Look at the first tumbling
run, in which Neculita's legs flash past the audience.

I taped it an a 4-head VHS VCR at SP, but I'm certain the degradation
is not due to the VCR; the distortion was non-local, time-varying, and
in just the regions one would expect a low-bit-rate video coder to
have problems.

Where in the chain from Barcelona does this occur?  Is satellite
bandwidth so scarce that NBC must resort to compressed NTSC?  How
might NBC be convinced to stop doing this, or at least use a better
coder?  Finally, if you have a tape of the afternoon coverage, take
a look and try to confirm that I'm not off my rocker.  For comparison,
NBC comes to me through WBZ, channel 4 in Boston, through the MIT cable
television system.

Peter Monta   monta@image.mit.edu
MIT Advanced Television Research Program
Xref: sparky comp.compression:2822 rec.video:9606 rec.video.satellite:3787 rec.video.production:1147
From: alehecka@sdcc13.ucsd.edu (MERLIN )
Newsgroups: comp.compression,rec.video,rec.video.satellite,rec.video.production
Subject: Re: Compression artifacts in NBC Olympic coverage
Date: 27 Jul 92 06:28:02 GMT
Followup-To: comp.compression
Organization: University of California, San Diego

Hey, only assholes like you try to mock up peple
for their ability to observe.  This is a compression
newsgroup and so it is forum to discuss any such observation.
So why don't you just shut up and let the people interested
in the subject to do their thing?
					MERLIN	
Newsgroups: comp.compression.research,comp.arch,comp.lang.c
From: awpaeth@watpix.waterloo.edu (Alan Wm Paeth)
Subject: C-language algorithm for finding a sparse bit (repost)
Organization: University of Waterloo
Date: Wed, 29 Jul 1992 22:58:36 GMT

A hand-transcription error butchered a line in the code previously posted.
Here is the full, unmolested test version used to derive the previous posting.
Many thanks to Dave Hudson (tdh@ksr.com) for bringing this to light.

   /Alan Paeth

----
int sparsebit(i)
    long i;
    {
    int p;
    p = 0;
/* return position 'p' on range [0..31] of a "lone bit" integer (value 2^p) */
/* otherwise, return -1. This is "little-Endian form" as the lsb is at p=0. */
    if (i == 0) return(-1);		/* no bits set */
    if ((i & (-i)) != i) return(-1);	/* two or more bits set */
    if (i & 0xAAAAAAAA) p++;
    if (i & 0xCCCCCCCC) p += 2;
    if (i & 0xF0F0F0F0) p += 4;
    if (i & 0xFF00FF00) p += 8;
    if (i & 0xFFFF0000) p += 16;
    return(p);
    }

int msbbit(i)
    long i;
    {
    long i2;
/* return the bit position of the msb as [0..31]; return -1 on arg of zero */
/*  if (i<0) return(31); */ /* speed-up assumes a 'long's msb is at pos 31 */
    while (i2 = (i & (i-1))) i = i2;
    return(sparsebit(i));
    }

main(argc, argv)
    char *argv[];
    {
    printf("%d\n", msbbit(atoi(argv[1])));
    }
From: darweesh@acsu.buffalo.edu (michael j darweesh)
Newsgroups: comp.compression.research
Subject: Re: Test Files for Compression/Source Code
Keywords: Source Code, Test Files
Date: 23 Jul 92 05:32:58 GMT
Organization: UB

Mark Nelson: The Data Compression Book,
ISBN (w/o IBM src disk): 1-55851-214-4 $26.95
	(w/ IBM src disk): 1-55851-216-0 $36.95

Very good book. The source code is in C and even a beginner can understand the
theories AND the C code (High level language exp. helps, but not nec.).
Main Topic List:
Data Compression History + Lexicon
Minimum Redundancy Coding (Huffman Coding, Shannon-Fano Alg)
Adaptive Huffman Coding
Arithmetic Coding (great stuff!)
Statistical Modeling
Dictionary-Based Compression
Sliding Window Compression (Lempel-Ziv 77 + LZSS)
Lempel-Ziv 78 + LZW
Speech Compression (lossless and lossy)
Lossy Graphics Compression (JPEG + DCT)
An Archiving package example (PC based)
There is some mention of patents in this book, but it isn't a good source
for that type of info.

There's lots-o-code and plenty of tables comparing performances.
The Bibliography and Afterward are even good.

The Data Compression Book is a must for every boy and girl who wants to
learn compression.

Enjoy,
Newsgroups: comp.compression.research
From: news@news2.cis.umn.edu (Usenet News Administration)
Subject: Re: Test Files for Compression/Source Code
Keywords: Source Code, Test Files
Organization: Electrical Engineering, U of MN, Mpls.
Date: Wed, 22 Jul 1992 21:45:36 GMT

This article was probably generated by a buggy news reader.
Newsgroups: comp.compression.research
From: mjjj@vax5.cit.cornell.edu
Newsgroups: comp.compression.research
Subject: ADPCM Help
Date: 21 Jul 92 15:34:03 EDT
Distribution: comp
Organization: Cornell University

Just wondering if anyone out there has any information regarding Adaptive Delta
Pulse Modulation Code (ADPCM) compression techniques.  I and a partner will be
attempting to write a real-time ADPCM convertor for a digital signal processor
and I could use any general information regarding the process as well as any
specifics you might know about actual code and programming.  Please respond to
me via e-mail at the following address:
podolsky@ee.cornell.edu

Thank you.
Matt Podolsky
From: bni@modulex.dk (Bent Nielsen)
Newsgroups: comp.compression.research
Subject: Re: ADPCM Help
Date: 22 Jul 92 16:20:03 GMT
Distribution: comp
Organization: A/S MODULEX, Copenhagen, Denmark

mjjj@vax5.cit.cornell.edu writes:
>Just wondering if anyone out there has any information regarding Adaptive Delta
>Pulse Modulation Code (ADPCM) compression techniques.  I and a partner will be
>attempting to write a real-time ADPCM convertor for a digital signal processor
>and I could use any general information regarding the process as well as any
>specifics you might know about actual code and programming.  Please respond to
>me via e-mail at the following address:
>podolsky@ee.cornell.edu

>Thank you.
>Matt Podolsky

I am also interested to receive this information
--
Bent Nielsen                Email : bni@modulex.dk
A/S MODULEX                 Phone : +45 44 53 30 11
Hoerkaer 20                 Fax :   +45 44 53 30 74
DK-2730 Herlev
Denmark
From: moss@cs.umass.edu (Eliot Moss)
Newsgroups: comp.compression.research
Subject: Re: Algorithm for finding set bits in a bit-string.
Date: 26 Jul 92 02:23:37 GMT
Reply-To: moss@cs.umass.edu
Organization: Dept of Comp and Info Sci, Univ of Mass (Amherst)
In-reply-to: aaronb@suhana.analog.ingr.com's message of 26 Jul 92 01:03:25 GMT

The "find first set bit" operation was recently discussed at length in
comp.arch, and could be relevant, especially if the one bits are sparse.  If
finding the one bits in a set is done frequently enough, and the ones are not
necessarily all that sparse, then you might want to do something like picking
up a byte and doing a 256 way switch statement (or indexing a pre-calculated
array, etc.) to avoid the bit by bit testing and looping. If you can tell
folks more about that your friend is trying to accomplish you get might get
higher quality suggestions :-). You should consider if comp.compress.research
is the right place for the discussion, too ....
--

		J. Eliot B. Moss, Associate Professor
		Department of Computer Science
		Lederle Graduate Research Center
		University of Massachusetts
		Amherst, MA  01003
		(413) 545-4206, 545-1249 (fax); Moss@cs.umass.edu
Newsgroups: comp.compression.research
From: aaronb@suhana.analog.ingr.com (Aaron B.)
Subject: Algorithm for finding set bits in a bit-string.
Keywords: Bit counting.
Reply-To: aaronb@suhana.analog.ingr.com
Organization: Home Office Enterprise
Date: Sun, 26 Jul 1992 01:03:25 GMT

I don't know where this request should belong, this is the closest group
I can find.  Anyway, this is my problem (my friend's actually):

Given a bit-string of any size print out the bits set starting with the
least significant bit.  This is an algorithm that I offered him.  But I
think there is much better way of doing it.


static unsigned char binvalue[9]={0x00, 0x01, 0x02, 0x04, 0x08,
                                        0x10, 0x20, 0x40, 0x80 };

int
show_msb(ch, off)
unsigned char ch;
long          off;
{
  int pos;

  if ( ch )
   {
     pos = ilog2( ch );
     printf("position = %d\n",pos+off);
     ch ^= binvalue[pos];         /* could also use: ch -= binvalue[pos]; */
     show_msb(ch, off);           /* recursive call for rest of bits */
   }
  return( 0 );
}

int
ilog2(n)
register unsigned char n;
{
   register long q;

   q = 0;
   while( n )
    {
      n >>= 1;
      q++;
    }
   return( q );
}   /* ilog2 */


Thanks in advance.

Aaron B
aaronb@suhana.analog.ingr.com
Newsgroups: comp.compression.research
From: taiwei@iti.gov.sg (Chua Tai Wei)
Subject: Fast DCT algorithm
Keywords: thanks
Organization: Information Technology Institute, National Computer Board, S'pore
Date: Fri, 31 Jul 1992 05:34:33 GMT

Thanks to all for the most helpful information on the above,   I will
be studing your replies most carefully...
 
Newsgroups: comp.compression.research
From: taiwei@iti.gov.sg (Chua Tai Wei)
Subject: Fast DCT algorithm
Summary: Looking for Fast DCT algorithm
Keywords: DCT
Organization: Information Technology Institute, National Computer Board, S'pore
Date: Sat, 25 Jul 1992 08:39:53 GMT


I am looking for efficient  Fast DCT algorithm to  implement Video
compression on a Sun workstation...


If you know where I can get some source code, algorithm or references,
please email to TAIWEI@iti.gov.sg.

Thank you...


Chua Tai Wei
AMTS
CCL-ITI
Newsgroups: comp.compression.research
From: linley@qucis.queensu.ca (Richard Linley)
Subject: Re: Fast DCT algorithm
Keywords: DCT
Organization: Computing & Information Science, Queen's University at Kingston
Date: Mon, 27 Jul 1992 17:36:45 GMT

In article <1992Jul25.083953.28947@iti.gov.sg> taiwei@iti.gov.sg (Chua Tai Wei) writes:
>
>I am looking for efficient  Fast DCT algorithm to  implement Video
>compression on a Sun workstation...
>

Me too!  Please write linley@qucis.queensu.ca

And thanks!

Newsgroups: comp.compression.research
From: gjnelson@ee.umn.edu (Grad student Greg Nelson)
Subject: Test Files for Compression/Source Code
Organization: University of Minnesota
Date: Wed, 22 Jul 1992 19:29:51 GMT

Followup-To: 
Distribution: 
Organization: Electrical Engineering, U of MN, Mpls.
Keywords: Source Code, Test Files
 
A good reference for various compression techniques is "The Data
Compression Book" by Mark Nelson, from M&T Books.  The book includes
chapters on Huffman, Lempel-Ziv, arithmetic coding, JPEG, and other
methods.  It also includes source code in the book and on IBM disk for
each of the compression methods it describes.  I believe it also
includes test files of various formats to demonstrate the methods and
provide benchmarks.

Newsgroups: comp.compression.research
From: eesfd@gdr.bath.ac.uk (F Dudbridge)
Newsgroups: comp.compression.research
Subject: Re: Fast DCT algorithm
Keywords: DCT
Date: 28 Jul 92 16:12:11 GMT
Organization: School of Electrical Engineering, University of Bath, UK

>>I am looking for efficient  Fast DCT algorithm to  implement Video
>>compression on a Sun workstation...

Two of my colleagues have just developed a fast DCT algorithm, but I
couldn't tell you how it works.  It will be submitted to Applied Statistics
soon.  Authors: B.Sherlock & D.Monro.
Newsgroups: comp.compression.research
From: pfreed@rp.CSIRO.AU ()
Subject: Re: Fast DCT algorithm
Keywords: DCT
Organization: CSIRO Division of Radiophysics/Australia Telescope National Facility
Date: Tue, 28 Jul 1992 01:16:48 GMT

I may have some help for you. The book
"Signal Processing with Lapped Transforms"
by Henrique S Malvar(Artech House 1992) has c 
code for two varieties of DCT transforms.
The relevant chapter gives the following reference
which may be useful :

Narasimha M.J. & A.M. Peterson "On the Computation of the
Discrete Cosine Transform", IEEE Trans Commun., vol COMM 25, Sep
1977, pp 1004-1009

-- 
Peter Freed		| As PIL would say : 
CSIRO Div. Radiophysics	| "This is not a signature file"
Signal & Imaging.	| The surgeon general warns that copying this signature
868 0498		| file may be detrimental to your health etc etc 
Newsgroups: comp.compression.research
From: praetzel@marconi.waterloo.edu (Eric Praetzel)
Subject: Re: Algorithm for finding set bits in a bit-string.
Organization: University of Waterloo
Date: Tue, 28 Jul 1992 16:40:45 GMT

In article <MOSS.92Jul25222337@ibis.cs.umass.edu> moss@cs.umass.edu writes:
>The "find first set bit" operation was recently discussed at length in
>comp.arch, and could be relevant, especially if the one bits are sparse.  If
  An interesting application is to locate point sources on a CCD scaned image.
In a virtual reality case here the sources of IR light are 4 LED emitters
mounted on the back of the helmet that holds 2 cameras.  The LEDs are not in
one plane so location of full spatial postion is possible.  By using a run
length encoding the 300 * 400 CCD map can be "compressed" and processed so
that when the data is read by the program most of the background 0's have
been compressed into a # representing the count.
  The result is that in real time (60 Hz) the computer (with a very limited
input bandwidth) can take in the compressed image, find the sources, refine
their location to about 1/3000 (center extraction) and do it in real time.
This is the only real world application I know of where data compression 
actually aided in processing of the data.
  And getting back around to square one.  All that this thing is, is a 
glorified set bit searcher  :-)
  As for S/W solutions, the best would be an array (assuming its a smallish
8 or maby 10 bit #) but that can vary depending upon architecture.  If its
a bigger number then just divide it into byte sized pieces and work your way
up thru the bytes.  This may or may not be faster than bit shift/test carry.
  - Eric 

Newsgroups: comp.compression.research
From: graef@rs1.hrz.th-darmstadt.de (Ulrich Graef)
Subject: Re: Fractal Compression
Date: Tue, 21 Jul 1992 12:08:53 GMT
Organization: TU Darmstadt

In article <1992Jul20.124331.126@ccsvax.sfasu.edu>, z_youngwd@ccsvax.sfasu.edu writes:
> This is in response to ALL the e-mail I've been getting in reference
> to compressing images using fractals. (actually partitioned iterated
> function systems)
> 
> Fractal-Based Image Compression
> Technical Report 1315, September 1989
> R.D. Boss, E.W. Jacobs
> 
> Fractal-Based Image Compression, II
> Technical Report 1362, June 1990
> E.W. Jacobs, R.D. Boss, Y. Fisher
> 
> Iterated Transform Image Compression
> Technical Report 1408, April 1991
> Y. Fisher, E.W. Jacobs, R.D. Boss
> 
> Studies of Iterated Transform Image Compression
> and its Application to Color and DTED
> Technical Report 1468, December 1991
> R.D. Boss, E.W. Jacobs
> 
> --- all of the above are technical reports from Naval Ocean Systems Center ---
> ------------------------------
> |                            |
> | Naval Ocean Systems Center |
> | San Diego, CA 92152-5000   |
> |                            |
> ------------------------------

How can I get these reports here in Europe. Are they available via ftp?

Uli

-- 
Ulrich Graef        |  analog (phone) :  +49 6155 62493           
Lichtenbergweg 11   |  digital (Email): graef@hrz.th-darmstadt.de 
D-W-6103 Griesheim  +--------------------------------------------
Germany             |  Nothing is real, look into your mirror!
Newsgroups: comp.compression.research,comp.arch,comp.lang.c
From: awpaeth@watpix.waterloo.edu (Alan Wm Paeth)
Subject: Re: Algorithm for finding set bits in a bit-string (and MSB).
Organization: University of Waterloo
Date: Tue, 28 Jul 1992 19:37:58 GMT

Given a 'very sparse' integer having only one bit set in position 'p', this
C fragment detects 'very sparseness' and returns p. It is based on two entries
appearing in _Graphics Gems II_ (Academic Press, 1992, ed: Jim Arvo). These
describe integer operations combining bitwise-logic and arithmetic to perform
sparesness tests, bit tallying, etc. (The two entries are by Ken Shoemake and
Alan Paeth; I've forgotten their exact titles).

int sparsebit(i)
    long i;
    {
    int p;
    p = 0;
/* return position 'p' on range [0..31] of a "lone bit" integer (value 2^p) */
/* otherwise, return -1. This is "little-Endian form" as the lsb is at p=0. */
    if (i == 0) return(-1);		/* no bits set */
    if ((i & (-i)) != i) return(-1);	/* two or more bits set */
    if (i & 0xAAAAAAAA) p++;
    if (i & 0xCCCCCCCC) p += 2;
    if (i & 0xF0F0F0F0) p += 4;
    if (i & 0xFF00FF00) p += 8;
    if (i & 0xFFFF0000) p += 16;
    return(p);
    }


The msb of a sparse word having any number of bits set can be found by using:

int msbbit(i)
    long i;
    {
    long i2;
/* return the bit position of the msb as [0..31]; return -1 on arg of zero */
    while (i2 = (i & (-i)) i = i2;
    return(sparsebit(i));
    }

which removes the set bits (if any) having least weight until merely the msb
remains and then invokes the first subroutine. (This is described in the second
Gem). Note that the first algorithm has worse-case running time which grows
by log2(W) for world length W: 32-bit longs and especially 64-bit longs are big
wins. The bit-discard loop of the second procedure has run time proportional to
the number of 'on' bits in the input. Its worst-case running time occurs when
called with an input of -1 (W passes through the loop).

When non-sparse input is anticipated the stock shift-and-test or byte-table
methods give much better average-case performance. In these cases msbbit()
can be sped up significantly with simple heuristics. For instance, a prefacing

    if (i < 0) return(-1);

in msbbit() gives fast returns for 50% of its input, including the worst case.

   /Alan Paeth
Newsgroups: comp.compression.research
From: grabenst@umbc4.umbc.edu (Mr. Michael Grabenstein; ACS (GUEST))
Subject: Re: Test Files for Compression/Source Code
Keywords: Source Code, Test Files
Organization: University of Maryland Baltimore Campus, Academic Computing Services
Date: Wed, 22 Jul 1992 20:45:36 GMT

In article <1992Jul22.192951.13159@news2.cis.umn.edu> gjnelson@ee.umn.edu (Grad student Greg Nelson) writes:
>Organization: Electrical Engineering, U of MN, Mpls.
> 
>A good reference for various compression techniques is "The Data
>Compression Book" by Mark Nelson, from M&T Books.  The book includes
>
	You also mentioned source code...What language? Hopefully C.
Also would you have the ISBN number?

Thanks.

Later,
	Mike
	ZMEG@AACC.bitnet
	or grabenst@umbc3.umbc.edu
Newsgroups: comp.compression
From: vijay@iitb.ernet.in (Vijay J. Talati)
Subject: KL transforms..
Organization: Indian Institute of Technology, Bombay
Date: Fri, 31 Jul 1992 11:56:03 IST

Hi,

Has anyone implemented a KL(Karhunen-Loeve) transforms based compression
technique. Is such a program available somewhere?

Actually, i am looking for algorithms that can compress SUN's audio files
(.au format) upto 20-30%.

Any pointers for the above are welcome. Please e-mail respones as
i do not read this group regularyly.

Thanks.
Vijay.
(vijay@gateway.iitb.ernet.in).
From: ep@id.dth.dk (Erik Plesner)
Newsgroups: comp.compression
Subject: Re: My New Compression Algorithm
Date: 17 Jul 92 08:00:16 GMT
Organization: Department of Computer Science

ed@titipu.meta.com (Edward Reid) writes:

>                                                   [..]  MY (tm) algorithm,
>for example, compresses every file to -1024 bits or less, and compresses most
[..]
>a negative megabit can hold an enormous amount of information, while saving
>unbelievable amounts of disk space as well.

Please mail me a -200MB file of yours - now THAT would increase my disk 
space.  (If I need more space later on, I just copy the -200MB file ).
  :-) .

Erik Plesner (ep@id.dth.dk)
Research Engineer, Technical University of Denmark.
Xref: sparky comp.compression:2849 rec.video:9700 rec.video.satellite:3835 rec.video.production:1178