输入纠错

/* Copyright (C) 2012 Chrisname.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */
#define MIN(a, b)	(((a) < (b)) ?  (a) : (b))
#define MAX(a, b)	(((a) > (b)) ?  (a) : (b))
#define ABS(x)		(((x) < 0)   ? -(x) : (x))

/**
 * A simple associative array.
 */
struct assoc_array {
	int		key;	/**< The key value. */
	const char*	value;	/**< The string value. */
};

/* Comparator for qsort(3) */
static int qsort_compare_keys(const void* p1, const void* p2)
{
	struct assoc_array* node1 = (struct assoc_array*)p1;
	struct assoc_array* node2 = (struct assoc_array*)p2;
	/* Return the difference between 'node1->key' and 'node2->key'
	 */
	return node1->key - node2->key;
}

/** Returns the absolute similarity score for 's1' and 's2' */
static int similarity(const char* s1, const char* s2)
{
	int score = 0;
	unsigned long len1 = strlen(s1), len2 = strlen(s2), len = MAX(len1, len2);
	int i = 0;
	/* Sum the absolute values of the differences between each character of
	 * s1 and s2 given by strcmp(3)
	 */
	while (len --> 0) {
		int abs;
		/* If one string has ended, compare the rest of the other string
		 * with zero. Otherwise, compare the two strings as normal.
		 */
		if (len1 >= i && len2 < i) {
			int x = 0 - s1[i];
			score += ABS(x);
		} else if (len2 >= i && len1 < i) {
			int x = 0 - s2[i];
			score += ABS(x);
		} else {
			abs = ABS(strcmp(s1 + i, s2 + i));
			score += abs;
			/* Skip past the non-matching char so we don't compare it again
			 */
			while (s1[i] == s2[i] && len > 0) {
				++i;
				--len;
			}
			++i;
		}
	}
	return score;
}

/**
 * \brief	Suggests corrections to user input.
 * \param key	The key string.
 * \param values An array of strings to compare with the key string.
 * \param count	The number of elements in array 'values'.
 * \param n	The number of outputs to print.
 * \param reverse Whether to print output in reverse.
 * \param detail Whether to print detailed information.
 */
void correct(const char* key, char* values[], int count, long n, int reverse, int detail)
{
	int i;
	struct assoc_array* aa = malloc(sizeof(struct assoc_array) * count);
	/* Build an associative array out of values
	 */
	for (i = 0; i < count; ++i) {
		aa[i].key   = similarity(key, values[i]);
		aa[i].value = values[i];
	}
	/* Sort 'aa' by key
	 */
	qsort(aa, count, sizeof(struct assoc_array), qsort_compare_keys);
	/* Print the values in key order
	 */
	if (n == 0)
		n = count;
	if (reverse) {
		if (n)
			n = MAX(n, count - n);
		while (n --> 0) {
			if (detail)
				printf("aa[%d] = { %d, %s }\n", n, aa[n].key,
								aa[n].value);
			else
				printf("%s\n", aa[n].value);
		}
	} else {
		if (n)
			n = MIN(n, count);
		for (i = 0; i < n; ++i) {
			if (detail)
				printf("aa[%d] = { %d, %s }\n", i, aa[i].key,
								aa[i].value);
			else
				printf("%s\n", aa[i].value);
		}
	}
	free(aa);
}