经常使用iciba进行单词查询， 关于他的搜索建议是通过单词前缀做的索引， 所以自己想动手实现下， 当然如果借助mysql的话，一条sql语句就能实现， 网上查询了下trie正适合做这个，所以通过C语言自己做了个demo
sug.c
/*
* 单词自动补全功能
* File: search.c
* Author: baijianmin
*/ #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <stdarg.h>
#include <time.h> #include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h> #define MAX_CHILD 26
#define LISTEN_PORT 8080
#define LOG_DEBUG_PATH "./logs/debug.log"
#define LOG_ERROR_PATH "./logs/error.log"
#define DATA_PATH "one.txt" /**
* define log level
*/
enum log_level {
DEBUG = ,
ERROR =
}; #define error(...) \
logger(ERROR, __LINE__, __VA_ARGS__) #define debug(...) \
logger(DEBUG, __LINE__, __VA_ARGS__) #define assert(expr, rc) \
if(!(expr)){ \
error(#expr"is null or 0"); \
return rc; \
} /**
* trie node
*/
typedef struct node_s {
int count;
struct node_s *child[MAX_CHILD];
char words[];
} node_t; /**
* global var
*/
node_t *global_root; /**
* get now timestr
*/
static void get_time(char *time_str, size_t len) {
time_t tt;
struct tm local_time;
time(&tt);
localtime_r(&tt, &local_time);
strftime(time_str, len, "%m-%d %H:%M:%S", &local_time);
} /**
* log
*/
static void logger(int flag, int line, const char *fmt, ...) {
FILE *fp = NULL;
char time_str[ + ];
va_list args;
get_time(time_str, sizeof(time_str)); switch (flag) {
case DEBUG:
fp = fopen(LOG_DEBUG_PATH, "a");
if (!fp) {
return;
}
fprintf(fp, "%s DEBUG (%d:%d) ", time_str, getpid(), line);
break;
case ERROR:
fp = fopen(LOG_ERROR_PATH, "a");
if (!fp) {
return;
}
fprintf(fp, "%s ERROR (%d:%d) ", time_str, getpid(), line);
break;
default:
return;
} va_start(args, fmt);
vfprintf(fp, fmt, args);
va_end(args);
fprintf(fp, "\n"); fclose(fp);
return;
} /**
* listen fro connections on a specified port
*/
int startup() {
int sockfd = -;
struct sockaddr_in addr;
memset(&addr, , sizeof (addr));
sockfd = socket(AF_INET, SOCK_STREAM, );
if (sockfd < ) {
error("socket fail: %s", strerror(errno));
return -;
}
addr.sin_family = AF_INET;
addr.sin_port = htons(LISTEN_PORT);
addr.sin_addr.s_addr = htonl(INADDR_ANY);
if (bind(sockfd, (struct sockaddr *) &addr, sizeof (addr))) {
error("bind fail: %s", strerror(errno));
return -;
}
if (listen(sockfd, )) {
error("listen fail: %s", strerror(errno));
return -;
}
return sockfd;
} /**
* create node
*/
node_t *createNode() {
node_t *node = (node_t *) calloc(, sizeof (node_t));
if (node == NULL) {
error("createNode fail: %s", strerror(errno));
}
} /**
* insert words
*/
int insert(node_t *root, char *words) {
if (!root || words[] == '\0') {
error("insert fail, root or words is null");
return -;
}
node_t *node = root;
node_t *tmp;
char *s = words;
while (*s != '\0') {
if (node->child[*s - 'a'] == NULL) {
tmp = createNode();
if (tmp == NULL) {
goto err;
}
node->child[*s - 'a'] = tmp;
}
node = node->child[*s - 'a'];
s++;
}
node->count++;
memcpy(node->words, words, strlen(words));
return ;
err:
return -;
} void search_child(node_t *node, int client_sock) {
if (!node) {
error("search_child fail, node is null");
return;
}
int i;
if (node->count) {
send(client_sock, node->words, strlen(node->words), );
send(client_sock, "|", , );
}
for (i = ; i < MAX_CHILD; i++) {
if (node->child[i]) {
search_child(node->child[i], client_sock);
}
}
} /**
* search
*/
int search(node_t *root, char *words, int client_sockfd) {
//--------------------------------fixme-------------------------------------
char *ps = words;
while (*ps != '\0') {
if (*ps < 'a' || *ps > 'z') {
*ps = '\0';
break;
}
ps++;
}
//--------------------------------------------------------------------------
if (!root || words[] == '\0') {
error("search fail, root or words is null");
return -;
}
debug("request query: %s", words);
char *s = words;
node_t *node = root;
while (*s != '\0') {
if (node->child[*s - 'a'] == NULL) {
break;
}
node = node->child[*s - 'a'];
s++;
}
if (*s == '\0') {
#if 0
if (node->count == ) {
printf("没有搜索到这个字符串，但是它是某个字符串的前缀\n");
} else {
printf("搜索到此字符串,出现次数为:%d\n", node->count);
}
#endif
search_child(node, client_sockfd); } else {
#if 0
printf("没有搜索到这个字符串:%s, %d\n", words, strlen(words));
#endif
}
close(client_sockfd);
} /**
* free mem
*/
void del(node_t *root) {
if (!root) {
error("del fail, root is null");
return;
} int i;
for (i = ; i < MAX_CHILD; i++) {
if (root->child[i]) {
del(root->child[i]);
}
}
free(root); } /**
* load data from file
*/
int load_data() {
global_root = createNode();
if(!global_root){
return -;
}
FILE *fp = fopen(DATA_PATH, "r");
if (!fp) {
error("open fail fail: %S", strerror(errno));
return -;
}
char words[];
while (!feof(fp) && fgets(words, sizeof (words), fp)) {
words[strlen(words) - ] = '\0';
insert(global_root, words);
memset(words, , sizeof (words));
}
debug("load_data success");
return ;
} /**
* response the request
*/
void accept_request(int client_sockfd){
char buf[];
memset(buf, , sizeof(buf));
recv(client_sockfd, buf, sizeof(buf), );
search(global_root, buf, client_sockfd);
//close client connection
close(client_sockfd);
} int main(void) {
int server_sockfd = -, client_sockfd = -;
struct sockaddr_in client_addr;
memset(&client_addr, , sizeof (client_sockfd));
int addr_len = sizeof (client_sockfd); server_sockfd = startup();
if (server_sockfd < ) {
return -;
} //load data from file
load_data(); //waitting for client
while () {
client_sockfd = accept(server_sockfd,
(struct sockaddr *) &client_addr, &addr_len);
if(client_sockfd < ){
error("accept fail, %s", strerror(errno));
return -;
}
accept_request(client_sockfd);
} close(server_sockfd);
return ;
}
sug.php
<?php
if($_GET['query']){
$query = $_GET['query'];
}else{
exit(json_encode(array()));
}
$host = "127.0.0.1";
$port = "8080";
$socket = socket_create(AF_INET, SOCK_STREAM, SOL_TCP) or die("Unable to create socket\n");
@socket_connect($socket, $host, $port) or die("Connect error.\n");
if ($err = socket_last_error($socket)){
socket_close($socket);
die(socket_strerror($err) . "\n");
}
$len = socket_write ($socket , $query, strlen($query));
$querys = "";
$ret = socket_read($socket, 100);
while($ret){
$querys.=$ret;
$ret = socket_read($socket, 100);
}
socket_close($socket);
$querysArr = explode("|", $querys);
array_pop($querysArr);
echo json_encode($querysArr);
效果：