Как сделать интерполяционный поиск по строкам? - PullRequest
Новая
       3

Как сделать интерполяционный поиск по строкам?

0 голосов
/ 04 апреля 2020

Я пытаюсь выполнить интерполяционный поиск, но я понял, что строки не могут быть как целые числа, что необходимо для функции поиска интерполяции. Я наткнулся на какое-то решение, например, на создание a = 1, b = 2 и т. Д., А затем добавил все это в другой целочисленный массив 

char c = 3;
char o = 15;
char w = 23;

и т. Д., Но это не совсем так. работает, когда я пытаюсь напечатать, per se 

print("%d", data[0]); which is cow, it shows another number, 6356204

Я пробовал это перед сортировкой данных. Я также нашел какое-то решение в Интернете, но оно в java, и я не могу понять, так как я знаю только язык c. 

#include <stdio.h>
#include<stdbool.h>
#include<string.h>
#include<stdlib.h>

int compare(const void *a, const void *b){

    const char *ia = (const char *)a;
    const char *ib = (const char *)b;

    return strcmp(ia, ib);
}

int SearchInterpolation(char * data[], int n, char searchKey){

    int position, low, high;
    low = 0;
    high = n-1;
    do{
        position = (searchKey - data[low]) * (high-low) / (data[high] - data[low]) + low;
        if(strcmp(data[position], searchKey) == 0) return position;
        if(strcmp(data[position], searchKey) > 0) high = position - 1;
        else low = position + 1;
    } while ((strcmp(searchKey, data[low])>0) && strcmp(searchKey, data[high]) < 0);
    return -1;
}

int main(int argc, char argv){

    char * data[10][50]={"cow", "sheep", "dog", "goat", "chicken", "duck", "bird", "fish", "bee", "horse"};
    char c = 3;
    char o = 15;
    char w = 23;
    print("test : %d\n", data[0]);
    int size1 = sizeof(data[0]);
    int n = sizeof(data) / size1;
    printf("%d\n\n", n);
    int i, j;
    char key[10];

    for(i = 0; i<n; i++){
        printf("%s\n", data[i]);
    }

    qsort(data, n, size1, compare);
    printf("=============\n\n");

    for(i = 0; i<n; i++){
        printf("%s\n", data[i]);
    }
    printf("\nSearch: "); scanf("%s", &key);
    fflush(stdin);

    int index = SearchInterpolation(data, n, key);

    if(index != -1){
        printf("%s found at index - %d", key, index);
    } else{
        printf("Data is not found");
    }

    return 0;
}

Я не могу понять, как изменить строки в целое число, может ли кто-нибудь любезно помочь мне сделать поиск интерполяции со строками?

1 Ответ

1 голос
/ 04 апреля 2020

Длина строки потенциально огромна, как если бы она была невероятно точной.

Две строки могут быть достаточно «близкими». Преобразование в число с последующим вычитанием потребовало бы большой точности. 

"abcdefghijklmnopqrst_x"
"abcdefghijklmnopqrst_y"

Как выполнить интерполяционный поиск по строкам?

Для интерполяции нам понадобятся оба символа numeric f_abs(string) (для общего значения) и numeric f_dif(string1, string2) (для полезных различий, даже если они почти равны).

Обратите внимание, что в конце используйте strcmp(string1, string2) для проверки на равенство.

I Рекомендуется использовать double. 

double f_abs(const char *s) {
  const unsigned char *us = (const unsigned char *) s;
  double val = 0.0;
  double f = 1.0;
  while (*us) {
    f /= UCHAR_MAX + 1;
    val += *us++ * f;
  }
  return val;
}

double f_dif(const char *s1, const char *s2) {
  const unsigned char *us1 = (const unsigned char *) s1;
  const unsigned char *us2 = (const unsigned char *) s2;
  double val = 0.0;
  double f = 1.0;
  while (*us1 && *us2) {
    f /= UCHAR_MAX + 1;
    val += (*us1++ - *us2++) * f; // difference taken before scaling
  }
  while (*us1) {
    f /= UCHAR_MAX + 1;
    val += *us1++ * f;
  }
  while (*us2) {
    f /= UCHAR_MAX + 1;
    val -=  *us2++ * f;
  }
  return val;
}

Даже double f_dif(s1, s2) будет бесполезен, если строки имеют общий префикс из 110 символов. После этого я рекомендую, чтобы код переходил от интерполяции к бисекции.

Поскольку словарь слов clumpy (группы слов "рядом" друг с другом), рассмотрите возможность чередования интерполяции с деление пополам, чтобы не застрять в областях, где интерполяция не полезна. BTDT

...