Home | History | Annotate | Line # | Download | only in bigram
locate.bigram.c revision 1.8 
      1 /*	$NetBSD: locate.bigram.c,v 1.8 2000/03/22 21:45:02 simonb Exp $	*/
      2 
      3 /*
      4  * Copyright (c) 1989, 1993
      5  *	The Regents of the University of California.  All rights reserved.
      6  *
      7  * This code is derived from software contributed to Berkeley by
      8  * James A. Woods.
      9  *
     10  * Redistribution and use in source and binary forms, with or without
     11  * modification, are permitted provided that the following conditions
     12  * are met:
     13  * 1. Redistributions of source code must retain the above copyright
     14  *    notice, this list of conditions and the following disclaimer.
     15  * 2. Redistributions in binary form must reproduce the above copyright
     16  *    notice, this list of conditions and the following disclaimer in the
     17  *    documentation and/or other materials provided with the distribution.
     18  * 3. All advertising materials mentioning features or use of this software
     19  *    must display the following acknowledgement:
     20  *	This product includes software developed by the University of
     21  *	California, Berkeley and its contributors.
     22  * 4. Neither the name of the University nor the names of its contributors
     23  *    may be used to endorse or promote products derived from this software
     24  *    without specific prior written permission.
     25  *
     26  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
     27  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     28  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     29  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
     30  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
     31  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
     32  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     33  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
     34  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
     35  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
     36  * SUCH DAMAGE.
     37  */
     38 
     39 #include <sys/cdefs.h>
     40 #ifndef lint
     41 __COPYRIGHT("@(#) Copyright (c) 1989, 1993\n\
     42 	The Regents of the University of California.  All rights reserved.\n");
     43 #endif /* not lint */
     44 
     45 #ifndef lint
     46 #if 0
     47 static char sccsid[] = "@(#)locate.bigram.c	8.2 (Berkeley) 4/28/95";
     48 #endif
     49 __RCSID("$NetBSD: locate.bigram.c,v 1.8 2000/03/22 21:45:02 simonb Exp $");
     50 #endif /* not lint */
     51 
     52 /*
     53  *  bigram < text > bigrams
     54  *
     55  * List bigrams for 'updatedb' script.
     56  * Use 'code' to encode a file using this output.
     57  */
     58 
     59 #include <stdio.h>
     60 #include <stdlib.h>
     61 #include <string.h>
     62 #include <sys/param.h>			/* for MAXPATHLEN */
     63 
     64 int	main __P((int, char **));
     65 static int compare_bigrams __P((const void *, const void *));
     66 static void add_bigram __P((u_char, u_char));
     67 
     68 static char buf1[MAXPATHLEN] = " ";
     69 static char buf2[MAXPATHLEN];
     70 
     71 struct bigram {
     72 	int count;
     73 	u_char b1, b2;	/* needed for final sorting */
     74 };
     75 
     76 struct bigram bigrams[256 * 256];
     77 
     78 static void
     79 add_bigram(i1, i2)
     80 	u_char i1, i2;
     81 {
     82 	if (i1 == '\n') {
     83 		bigrams[0].count++;
     84 		i1 = 0;
     85 	}
     86 	if (i2 == '\n') {
     87 		bigrams[0].count++;
     88 		i2 = i1;
     89 		i1 = 0;
     90 	}
     91 
     92 	bigrams[(i1<<8)+i2].count++;
     93 }
     94 
     95 static int
     96 compare_bigrams(item1, item2)
     97 	const void *item1, *item2;
     98 {
     99 	const struct bigram *it1=item1, *it2=item2;
    100 
    101 	if (it1->count != it2->count)
    102 		return it2->count - it1->count;
    103 	else if (it1->b1 != it2->b1)
    104 		return it2->b1 - it1->b1;
    105 	else
    106 		return it2->b2 - it2->b2;
    107 }
    108 
    109 int
    110 main(argc, argv)
    111 	int argc;
    112 	char *argv[];
    113 {
    114   	char *cp;
    115 	char *oldpath = buf1, *path = buf2;
    116 	struct bigram *bg;
    117 	int i;
    118 
    119 	/* initialize bigram array */
    120 	memset(bigrams, 0, sizeof(bigrams));
    121 	for(i=0; i < 65536; i++) {
    122 		bigrams[i].b1 = i / 256;
    123 		bigrams[i].b2 = i % 256;
    124 	}
    125 
    126      	while ( fgets ( path, sizeof(buf2), stdin ) != NULL ) {
    127 
    128 		/* skip longest common prefix */
    129 		for ( cp = path; *cp == *oldpath; cp++, oldpath++ )
    130 			if ( *oldpath == '\0' )
    131 				break;
    132 
    133 		/*
    134 		 * output post-residue bigrams only
    135 		 */
    136 		for(; cp[0] != '\0' && cp[1] != '\0'; cp += 2)
    137 			add_bigram((u_char)cp[0], (u_char)cp[1]);
    138 
    139 		if (path == buf1)		/* swap pointers */
    140 			path = buf2, oldpath = buf1;
    141 		else
    142 			path = buf1, oldpath = buf2;
    143    	}
    144 
    145 	/* sort the bigrams by how many times it appeared and their value */
    146 	heapsort((void *)bigrams, 256 * 256, sizeof(struct bigram),
    147 			compare_bigrams);
    148 
    149 	/* write 128 most frequent bigrams out */
    150 	bg = bigrams;
    151 	for (i = 0; i < 128 && bg->count > 0; i++, bg++) {
    152 		if (bg->b1 != '\0')
    153 			fputc(bg->b1, stdout);
    154 		if (bg->b2 != '\0')
    155 			fputc(bg->b2, stdout);
    156 	}
    157 
    158 	return (0);
    159 }
    160