поиск строки в списке диапазонов строк

Question

У меня есть список лексикографических диапазонов, например, [a,an) [an,bb) [bb,d) [c,h) Учитывая строку, скажем apple, мне нужно найти, к какому диапазону она принадлежит.В этом случае это во втором диапазоне.Если строка может принадлежать нескольким диапазонам, необходимо вернуть первый.Например: cat должен возвращать range3, а не range4.

Подход с использованием грубой силы будет заключаться в циклическом просмотре списка по порядку и проверке, подходит ли строка туда.Лучше было бы сначала разрешить перекрытия, отсортировать диапазоны и выполнить бинарный поиск.Есть предложения по дальнейшей оптимизации алгоритма?Также приветствуются советы по реализации C ++.Эта логика происходит на критическом пути выполнения и должна быть быстрой.

Обновление: Да, в диапазонах могут быть пробелы.Да, бинарный поиск может сделать это O(log(n)).Можно ли как-нибудь придумать хеш и сделать его еще лучше?Как будет выглядеть хеш?Мы можем предположить, что у нас есть только строчные символы во всех строках и диапазонах.

Answer 1

Вот что вы должны сделать:

Сначала отсортируйте диапазоны по их началам в лексикографическом порядке. Затем вы должны выполнить следующую предварительную обработку для них - для каждого диапазона сделать его начало большим, чем начало и конец предыдущего диапазона (если это делает текущий диапазон пустым, просто проигнорируйте его). Вы делаете это потому, что если слово находится перед концом предыдущего диапазона, оно будет принадлежать некоторым из предыдущих диапазонов и никогда не будет классифицировано в текущем. После этой предварительной обработки все диапазоны не перекрываются, поэтому каждое искомое слово будет принадлежать не более одному из них. Поэтому все, что вам нужно сделать, - это выполнить бинарный поиск по результирующим предварительно обработанным диапазонам, который будет иметь сложность O (log (n)). Я сомневаюсь, что вы можете добиться большей сложности для этой проблемы.

Answer 2

Какой-то указатель на начало каждого диапазона, возможно, двоичное дерево, вероятно, будет хорошей идеей.Не уверен, если вам нужно индексировать до конца каждого диапазона, если не может быть пробелов.

Answer 3

Мой подход будет

• диапазон имеет два предела (нижний и верхний предел)
• каждый диапазон делит пространство на три части (внизу, внутри, сверху)
• каждый предел делит пространство на две части (ниже, выше_или_эквивалент)

Таким образом, метод может быть:

• номер диапазона
• разложить диапазоны на два предела
• помещает ограничения в дерево, в узлах, содержащих два списка с диапазонами, которые к ним относятся (один список для узлов, которые используют этот предел в качестве нижнего предела, один для верхнего предела)
  • эти списки могут быть растровыми изображениями, так как диапазоны нумеруются
• найти строку
  • вы идете по дереву, и каждый раз, когда вы уходите, вы фактически пересекаете лимит и получаете знания о том, какие у вас есть границы справа / слева и в каких диапазонах вы находитесь слева / справа / внутри.
  • вам нужно два дополнительных списка (с номерами диапазонов) для этого обхода.
  • эти списки могут быть растровыми
  • каждый раз, когда вы пересекаете границу, вы добавляете номер диапазона из одного из списков и удаляете его из другого.
• как только вы попадаете в диапазон (x> = нижний предел && x <верхний предел; <em>с пределами, соответствующими тому же диапазону курса ), алгоритм заканчивается.
  • (учитывая, что это на самом деле диапазон с наименьшим числом: первое совпадение)
  • это можно обнаружить, если два списка имеют одного или нескольких участников
  • нам нужен перекрывающийся элемент с наименьшим номером.

Поскольку этот метод представляет собой поиск по дереву, он имеет сложность O (log (N)).

ОБНОВЛЕНИЕ: если подумать, растровые изображения не являются хорошим способом хранения списков использования или результатов. Связанный список (фактически два) лучше. Код 300 строк. Должен ли я разместить его здесь?

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

#define COUNTOF(a) (sizeof a / sizeof a[0])
#define WANT_DUPLICATES 0

struct range {
                /* separate linked lists for {lo,hi}) 
                ** for limits that this range participates in. */
        struct range *next_lo;
        struct range *next_hi;
        unsigned num;
        char *str_lo, *str_hi;
        } ranges[] =
{{NULL,NULL,0, "a","an"}, {NULL,NULL,1, "an", "bb"}
,{NULL,NULL,2, "bb", "d"}, {NULL,NULL,3, "c", "h"}
,{NULL,NULL,4, "bb", "c"}, {NULL,NULL,5, "c", "d"}
};
#define NRANGE COUNTOF(ranges)

void add_range(struct range *pp);
void list_dmp(FILE *fp, int isupper, struct range *bp);

struct treetwo {
        struct treetwo *prev;
        struct treetwo *next;
        char *str;
        struct range *list_lo; /* ranges that use str as lower limit */
        struct range *list_hi; /* ranges that use str as upper limit */
        };

struct treetwo *root = NULL;
struct treetwo ** find_hnd(struct treetwo **tpp, char *str);
void tree_dmp(FILE *fp, struct treetwo *tp, char *msg, unsigned indent);

struct result {
        unsigned size;
        unsigned used;
        struct {
                unsigned num;
                unsigned mask;
                } *entries;
        };
#define MASK_BELOW_LO 1
#define MASK_ABOVE_LO 2
#define MASK_BELOW_HI 4
#define MASK_ABOVE_HI 8

int result_resize(struct result *res, unsigned newsize);
void init_structures(void);
struct result *find_matches (char *str);
unsigned update_state(struct result *rp, struct treetwo *tp, int isabove);

int main (void)
{
char buff[100];
struct result *res;
size_t pos;
unsigned idx;
static char *legend[4] = { "unknown", "below", "above",  "impossible"};

init_structures();
tree_dmp(stderr, root, "Root", 0);

while (fgets (buff, sizeof buff, stdin) ) {
        pos=strcspn(buff, "\r\n");
        buff[pos] = 0;
        res = find_matches (buff);
        for (idx=0; idx < res->used; idx++) {
                unsigned num = res->entries[idx].num;
                unsigned mask = res->entries[idx].mask;
                fprintf(stdout, "[%u]Range%u %x: '%s' %s '%s' and '%s' %s '%s'\n"
                        , idx, num, mask
                        , buff, legend[mask & 3], ranges[num].str_lo
                        , buff, legend[(mask>>2) & 3], ranges[num].str_hi
                        );
                }
        }

return 0;
}

unsigned update_state(struct result *rp, struct treetwo *tp, int isabove)
{
struct range *p;
unsigned mask_lo, mask_hi;
unsigned hitcnt,idx;
/* State: (lower limit)
** 0 : unknown
** MASK_BELOW_LO: below limit
** MASK_ABOVE_LO: above limit
** 3: impossible
** State: (upper limit)
** 0 : unknown
** MASK_BELOW_HI: below limit
** MASK_ABOVE_HI: above limit
** c: impossible
** Combined states:
** required state 2|4 := 6
** 5: unreachable
** a: unreachable
** 9: impossible
** f: impossible
*/

if (!tp) return 0;
hitcnt=0;
mask_lo = (isabove>=0) ? MASK_ABOVE_LO : MASK_BELOW_LO;
mask_hi = (isabove>=0) ? MASK_ABOVE_HI : MASK_BELOW_HI;

fprintf(stderr , "Update_state(start{%s}, isabove=%d, mask=%x,%x)\n"
        , tp->str , isabove, mask_lo, mask_hi);
fprintf(stderr , "Update_state(Lo=%s)=", tp->str);
list_dmp(stderr , 0, tp->list_lo);
idx=0;
for (p = tp->list_lo; p ; p = p->next_lo) {
        unsigned num = p->num;
        fprintf(stderr , "Update_state:[%u] |= %u", num, mask_lo );
        for (   ;idx < rp->used;idx++) { if (rp->entries[idx].num >= num) break; }
        if ( idx < rp->used ) {
                fprintf(stderr , " Old was:%u\n", rp->entries[idx].mask );
                rp->entries[idx].mask |= mask_lo;
                if (rp->entries[idx].mask == (MASK_ABOVE_LO|MASK_BELOW_HI)) hitcnt++;
                continue;
                }
        if ( idx >= rp->used) {
                if ( rp->used >= rp->size && result_resize(rp, rp->size ? rp->size*2 : 8)) break;
                fprintf(stderr , " New at:%u\n", idx );
                rp->entries[idx].num = num;
                rp->entries[idx].mask = mask_lo;
                rp->used++;
                }
        }

fprintf(stderr , "Update_state(Hi=%s)=", tp->str);
list_dmp(stderr , 1, tp->list_hi);
idx=0;
for (p = tp->list_hi; p ; p = p->next_hi) {
        unsigned num = p->num;
        fprintf(stderr , "Update_state:[%u] |= %u", num, mask_lo );
        for (   ;idx < rp->used;idx++) { if (rp->entries[idx].num >= num) break; }
        if ( idx < rp->used ) {
                fprintf(stderr , " Old was:%u\n", rp->entries[idx].mask );
                rp->entries[idx].mask |= mask_hi;
                if (rp->entries[idx].mask == (MASK_ABOVE_LO|MASK_BELOW_HI)) hitcnt++;
                continue;
                }
        if ( idx >= rp->used) {
                if ( rp->used >= rp->size && result_resize(rp, rp->size ? rp->size*2 : 8)) break;
                fprintf(stderr , " New at:%u\n", idx );
                rp->entries[idx].num = num;
                rp->entries[idx].mask = mask_hi;
                rp->used++;
                }
        }
return hitcnt;
}

struct result *find_matches (char *str)
{
int rc;
struct treetwo **hnd;
struct result *res = malloc (sizeof *res);
unsigned dst,src;
res->used=res->size=0; res->entries=0;

for (hnd= &root; *hnd; hnd = (rc < 0) ? &(*hnd)->prev : &(*hnd)->next ) {
        rc = strcmp( str, (*hnd)->str);
        fprintf(stderr, "####\nStr=%s Node={%s} rc=%d\n"
                , str, (*hnd)->str, rc );
        list_dmp(stderr , 0, (*hnd)->list_lo );
        list_dmp(stderr , 1, (*hnd)->list_hi );
        rc = update_state(res, *hnd , rc);
#if WANT_DUPLICATES
        continue;
#else
        /* if we don't want duplicates we can bail out on the first match */
        if (rc) break;
#endif
        }


/* Now cleanup the results.
** Below(lower limit) and above(upper limit) and variations can be removed.
** Some results are incomplete, because one of there limits is out
** of reach (shadowed by a narrower range).  We'll have to recompute these.
** The result structure is compacted: if entries are deleted, the remaining ones are shifted down.
** Note: part of this cleanup (removal of unreacheables) could be done in update_state(),
** that would keep the array with partial results as short as possible.
*/
for (dst=src=0; src < res->used; src++) {
        int rc;
        unsigned num = res->entries[src].num;
rescan:
        switch (res->entries[src].mask & 0xf) {
        default: break;
        case 0: /* impossible */
                goto rescan;
#if WANT_DUPLICATES
        case MASK_ABOVE_LO:
                rc = strcmp(str, ranges[num].str_hi);
                res->entries[src].mask |= (rc >=0) ? MASK_ABOVE_HI : MASK_BELOW_HI;
                goto rescan;
        case MASK_BELOW_HI:
                rc = strcmp(str, ranges[num].str_lo);
                res->entries[src].mask |= (rc >=0) ? MASK_ABOVE_LO : MASK_BELOW_LO;
                goto rescan;
#endif
        case MASK_BELOW_HI|MASK_ABOVE_LO:
                if (dst != src) res->entries[dst] = res->entries[src];
                dst++;
                }
        }
fprintf(stderr, "####\nFinal pass: %u/%u\n", dst, res->used );
res->used = dst;
return res;
}

void init_structures(void)
{
unsigned idx;

for (idx = 0; idx < NRANGE; idx++) {
        add_range( &ranges[idx]);
        }
}

void list_dmp(FILE *fp, int isupper, struct range *bp)
{

fprintf(fp, "%s", (isupper) ? "Upper" :"Lower"  );
for (   ; bp  ; bp = (isupper) ? bp->next_hi : bp->next_lo) {
        fprintf(fp, " %u:{%s,%s}"
        , bp->num , bp->str_lo , bp->str_hi
        );
        }
fprintf( stdout, "\n" );
}

void add_range(struct range *pp)
{
struct treetwo **tpp;
struct range **rpp;

fprintf(stderr, "Inserting range %u->{%s,%s}\n", pp->num, pp->str_lo, pp->str_hi);
        /* find low boundary for this interval */
tpp = find_hnd (&root, pp->str_lo);
if (!*tpp) {
        fprintf(stderr, "Creating node for %u->%s (low)\n", pp->num, pp->str_lo);
        *tpp = malloc(sizeof **tpp);
        (*tpp)->list_lo = NULL;
        (*tpp)->list_hi = NULL;
        (*tpp)->str = pp->str_lo;
        }
for (rpp = &(*tpp)->list_lo; *rpp ; rpp = &(*rpp)->next_lo) {;}
*rpp = pp;
fprintf(stderr, "Added range %u->{%s,%s} to treenode(%s)->list_lo\n"
        , pp->num, pp->str_lo, pp->str_hi
        , (*tpp)->str
        );

        /* find high boundary */
tpp = find_hnd (&root, pp->str_hi);
if (!*tpp) {
        fprintf(stderr, "Creating node for %u->%s (High)\n", pp->num, pp->str_hi);
        *tpp = malloc(sizeof **tpp);
        (*tpp)->list_lo = NULL;
        (*tpp)->list_hi = NULL;
        (*tpp)->str = pp->str_hi;
        }
for (rpp = &(*tpp)->list_hi; *rpp ; rpp = &(*rpp)->next_hi) {;}
*rpp = pp;
fprintf(stderr, "Added range %u->{%s,%s} to treenode(%s)->list_hi\n"
        , pp->num, pp->str_lo, pp->str_hi
        , (*tpp)->str
        );
}

struct treetwo ** find_hnd(struct treetwo **tpp, char *str)
{
int rc;

for (   ; *tpp; tpp = (rc < 0) ? &(*tpp)->prev : &(*tpp)->next ) {
        rc = strcmp( str, (*tpp)->str);
        if (!rc) break;
        }
return tpp;
}

void tree_dmp(FILE *fp, struct treetwo *tp, char *msg, unsigned indent)
{
unsigned uu;
if (!tp) return;
if (!msg) msg = "";

for (uu=0; uu < indent; uu++) { fputc( ' ', fp); }
fprintf(fp, "%s:{%s}\n", msg, tp->str );

for (uu=0; uu < indent+1; uu++) { fputc( ' ', fp); }
list_dmp(fp , 0, tp->list_lo);

for (uu=0; uu < indent+1; uu++) { fputc( ' ', fp); }
list_dmp(fp , 1, tp->list_hi);

tree_dmp(fp, tp->prev, "Prev", indent+2);
tree_dmp(fp, tp->next, "Next", indent+2);
}
int result_resize(struct result *res, unsigned newsize)
{
void *old;

old = res->entries;
res->entries = realloc ( res->entries , newsize * sizeof *res->entries);
if ( !res->entries) {
        res->entries = old; return -1;
        }
res->size = newsize;
if (res->used > newsize) res->used = newsize;
return 0;
}

Answer 4

Меня не удивит, что ваш набор диапазонов может быть представлен с помощью дерева (http://en.wikipedia.org/wiki/Trie). После заполнения дерева время запроса не должно превышать ни длину самого длинного диапазона, ни длину строки запроса .

Это оптимально с точки зрения времени запроса (фактически O (1) в вашей вычислительной модели).

Answer 5

Вы можете подойти к этому "gridding".

Использовать массив с 26 записями, соответствующими первой букве. Каждый бин содержит список диапазонов, имеющих непустое пересечение с ним. Как

'a' -> [a,an) [an,bb), 'b' -> [an,bb) [bb,d), 'c' -> [bb,d) [c,h) ...

Вы легко обобщаете идею на префикс из нескольких букв

'aaa' -> [a,an), 'aab' -> [a,an), 'aac' -> [a,an) ...

Это может значительно сократить список проверяемых диапазонов, особенно если есть небольшие совпадения, за счет хранения и времени предварительной обработки.

Для обозначения того, что мусорное ведро полностью закрыто, можно использовать специальное соглашение.

Счастливые распределения могут привести к O (1), я думаю.

Answer 6

Если у вас есть запасная память и ограничены строчными буквами, вы можете построить многоцелевое дерево. Верхний узел имеет массив из 26 указателей. Указатели равны нулю, если диапазон не начинается с этого символа. Они указывают на диапазон, если все слова, начинающиеся с этого символа, попадают в диапазон, и указывают на другой узел, если диапазоны разделяются на следующий символ. (с учетом [aa-ap], [ar-bl]; запись 'a' будет указывать на другой узел, где записи с 'a' по 'p' указывают на диапазон 1, запись 'q' была нулевой, а 'r' через 'z' указывает на диапазон 2.)

Это должно быть O (max (range_specifier)).

Answer 7

Мне приходит в голову одно решение, может быть, вы можете отсортировать слово apple и определить, какой символ идет последним в аз-порядке.И просто проверьте, есть ли один символ в ваших диапазонах.Думая больше ...