На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное DigiMania RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: shadeofgray, JoeUser
  
> Поясните по алгоритму "Хеширование по сигнатуре", очень многое непонятно
    Всем хай! Сходу к делу!

    Правильно ли я понимаю, что, если даны слова и допускается неточное совпадение до 1 ошибки, то нужно действовать так.
    Допущения:
    1. Слова могут состоять только из малых латинских букв (их всего 26 штук).

    Сравниваемые слова: "arrow", "xuxbp".
    Алгоритм:
    1. Вычисляем длины слов. Если длины слов НЕ РАВНЫ, то они НЕ совпадают. В данном случае = 5 букв. ОК.
    2. Т к длины слов = 5 букв, то потребуется битовый массив из 5 элементов.
    3. Нужно разбить алфавит (26 букв) так на группы, чтобы все они уместились в 5 групп. 26 mod 5 = 5 групп. Причем в последней группе будет 6 символов.
    4. Привожу картинку, где показан процесс хеширования.
    Прикреплённая картинка
    Прикреплённая картинка

    Выводы:
    битовые хеши данных слов:
    arrow ---> 10111
    xuxbp ---> 10011
    Разница лишь в 3-ем бите, следовательно, можно считать, что данные слова ПОХОЖИ! Но это ведь не так) вроде...
    ===================================================
    Вопросы:
    1. Правильно ли я понимаю, что длины заданных слов должны быть равны? Но с др.стороны, например слова "hel" и "hell" отличаются лишь 1-й буквой.
    2. Насколько правильно делается этап в алгоритме №3 (разбивка на группы символов)? В данном случае получилось 5-6 слоев букв, возможно, нужно сделать было в 2 слоя, т е 13 групп по 2 символа.
    3. Правильно ли я понимаю, что алгоритм хеширования по сигнатуре един для всех случаев, т е хеш-функция работает ВСЕГДА по одной схеме? Др.словами, нельзя иметь ТРИ хеш-функции, которые используют хеширование по сигнатуре.

    Скрытый текст
    P.S. если честно, то в сети я не смог найти понятного мне описания этого алгоритма. Какой-то фрагмент есть на Хабре и еще кое-где обрывочно как-то и обобщенно! Статью Бойцова не смог найти. Помню, когда искал алгоритм определения мостов или шарниров в графе, то попалась изумительная статья Лахно. Это, пожалуй, была лучшая статья в этой тематике, которую когда-либо читал). Автор без академического занудства четко изложил алгоритм + поэтапно показал в красивых комиксах все этапы до мелочей. Пример его кода был вроде на Паскале, мне нужно было на СИ. Прочитав его статью раз 7-8 сумел С 1-го РАЗА закодировать правильно на СИ. Попадись мне на глаза нечто подобное по хешированию по сигнатуре, думаю, смог бы разобраться сам...Повторю, статья Лахно на мое малое ИМХО великолепна до предела :whistle:
    I originate
    You must appreciate, all the others imitate

    SCOOTER "GUEST LIST"

    'Pon the mic I'm the teacher!
    Spread my words like a preacher!
    Yiiihhaaaa!!!!

    SCOOTER "WEEKEND"
      1. При длине хешей меньше исходных данных имеется довольно высокая вероятность коллизии.
      2. Хэш-функцию можно придумать самому.
      Сообщение отредактировано: Gonarh -
        FasterHarder
        Вы неправильно указали название алгоритма. Не помню как правильно битовый хэш или что-то в этом роде.
        "Хеширование по сигнатуре" - это название научной проблемы, а не конкретного алгоритма. Как было верно замечена функций для хеширования можно придумать много. Но у данной проблематики суть в том что идентификаторы короткие и большинство функций дают большое число коллизий.
        Цитата FasterHarder @
        Правильно ли я понимаю, что длины заданных слов должны быть равны? Но с др.стороны, например слова "hel" и "hell" отличаются лишь 1-й буквой.

        Длина идентификатора(сигнатуры) обычно ограниченна. Взять компиляторы 60-тых годов там 4 байта для идентификатора. У современных 256 и более. Идентификаторы заносились в символьные таблицы, где под идентификатор заранее отведён массив фиксированной длины. Соответственно недостающие символы кодируются нулевым символом.


        Цитата FasterHarder @
        Разница лишь в 3-ем бите, следовательно, можно считать, что данные слова ПОХОЖИ! Но это ведь не так) вроде...

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

        Цитата
        Насколько правильно делается этап в алгоритме №3 (разбивка на группы символов)? В данном случае получилось 5-6 слоев букв, возможно, нужно сделать было в 2 слоя, т е 13 групп по 2 символа.

        Это не важно. Длину результат хэш-функции по традиции подбирается под длину машинного слова 8,16,32,64 бита. Во времена без кэшивых процессоров длина машинного слова определяла скорость работы программы.
        Правильный обед должен состоять из 5 блюд приготовленных из 33 ингредиентов.
          Gonarh, ок, если ты разбираешься в этом алго, то скажи, мое решение правильное?

          Цитата Pavia @
          Похожи если бы у них хэши совпали, а так различны.

          когда читал обрывочное описание, то было сказано, что отличие в 1-м бите допустимо типа на похожесть. Можно ввести 2бита отличности и тоже считать похожими и т.д.

          Цитата Pavia @
          Это не важно.

          это ты сейчас озвучил. А в статейках, где есть хоть какое-то подобие примеров, ширина битовой сетки = кол-ву символов хешируемого слова. Теперь мне стало еще более непонятно!

          Но, к примеру, если разбить латинские буквы на 13 групп по 2 символа (13 бит), то в результате РЕЗКО возрастает коэффициент похожести (см.картинку)
          Прикреплённая картинка
          Прикреплённая картинка


          Как я понял, хеширование по сигнатуре сравнивает НЕ по похожести звучания (алг.soundex), а по написанию, при этом говорят, что порядок букв не важен.
          Я чегот не выкупаю все больше и больше! Почему не учитывают частотность встречаемости каждой буквы и т.п.
          I originate
          You must appreciate, all the others imitate

          SCOOTER "GUEST LIST"

          'Pon the mic I'm the teacher!
          Spread my words like a preacher!
          Yiiihhaaaa!!!!

          SCOOTER "WEEKEND"
            Цитата FasterHarder @
            Почему не учитывают частотность встречаемости каждой буквы и т.п.

            Сложение 1 так сдвиг 1 такт. Учёт частотности это выборка из памяти 4 такта.
            Учитывать можно, но это снизит скорость расчёта ХЭШ-функции.

            Цитата FasterHarder @
            когда читал обрывочное описание, то было сказано, что отличие в 1-м бите допустимо типа на похожесть. Можно ввести 2бита отличности и тоже считать похожими и т.д.

            Когда автор писал это у него в голове гуляли тараканы и дул ветер. Так что тут стоит уточнить у него о чём он думал.

            Ваш алгоритм можно описать проще. Возьмём идентификатор
            01011010 01011010 01011010 01011010
            Вы кинем каждый второй бит.
            00110011 00110011
            На компах с середины 90-тых это выполняется одной машинной командой такта за 2 без учёта загрузки выгрузки.

            Изменилась буква в слове и мы видим "if" "is" "as" и мы видим что биты поменяются.
            Работает алгоритм быстро. Поиск в ХЭШ-таблицы быстрый вставка тоже быстрая.
            Можно применять алгебру-множеств(Алгебру-СУБД) - пересечение объединение.
            Каждая четверка соответствует одному байту казалось бы это удобно НО.
            После пересечения множеств всё равно придётся делать проверку по всей таблицы на коллизии, а их будет очень много. Поэтому для СУБД это не годится. А что же с трансляторами?


            Проблема в том что в ЯП пол текста состоит из идентификаторов "i","j". И это даст на каждом втором идентификаторе коллизию. А коллизии требует долгой обработки. И не только i/j, do/else и таких случае очень много. Когда как Вирт спроектировал свою ХЭШ-функцию так что-бы у него коллизий было менее 3% при проходе по тексту программы. Это значит что выборка слова из ХЭШ-таблице у Виртом будет работать в 2-4 раза быстрее чем ваша. А так как эта операция занимает 90% времени, то соответственно его транслятор будет работать быстрее чем Ваш(вашего Автора).
            Поэтому я пишу что у автора тараканы в голове. Так как такая похожесть выходит боком.
            Сообщение отредактировано: Pavia -
            Правильный обед должен состоять из 5 блюд приготовленных из 33 ингредиентов.
              Pavia, это все околоалгоритмические размышления! )

              дай, мне, плиз, если хочешь/можешь точные инструкции по этому алгоритму
              Например:
              1. Определяем алфавит заданных слов (пусть мощность M)
              2. Сравнению подлежат только слова одинаковой длины
              3. Если длина слова n, то бить нужно на такое-то кол-во групп алфавит
              etc

              Или фишка в том, что здесь нет как такого алгоритма строгого, а все зависит от входных данных?

              На данный момент я НЕ ПОНИМАЮ, что нужно делать)

              P.S. Вирт - безусловно крут)
              I originate
              You must appreciate, all the others imitate

              SCOOTER "GUEST LIST"

              'Pon the mic I'm the teacher!
              Spread my words like a preacher!
              Yiiihhaaaa!!!!

              SCOOTER "WEEKEND"
                FasterHarder
                Цитата
                это все околоалгоритмические размышления! )

                Это алгоритмические рассуждения. Только они практические, а не чисто теоретические. Теоретически что у Вас что у Вирта сложность алгоритма O(1). А практически T1(n)>T2(n). И именно оптимизация этого времени интересна.

                А у вас всегда так. Шаг в сторону и Вы теряетесь. Что делать если Ваш автор не дал точного описания? А вариантов доработки и применения куча?
                Цитата
                1. Определяем алфавит заданных слов (пусть мощность M)

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

                Цитата FasterHarder @
                Или фишка в том, что здесь нет как такого алгоритма строгого, а все зависит от входных данных?

                Да зависит от входных данных и именно в этом фишка хеширование идентификаторов. Кнут, Вирт, Эхо все они это описали.

                Цитата FasterHarder @
                3. Если длина слова n, то бить нужно на такое-то кол-во групп алфавит

                Я бы добавил "максимальная", т.е "максимальная длина слова".

                Цитата FasterHarder @
                На данный момент я НЕ ПОНИМАЮ, что нужно делать)

                А кто кроме вас будет понимать что вы там делаете, безвольный Вы наш?

                Цитата
                то бить нужно на такое-то кол-во групп алфавит

                Очевидно же что разбиение зависит от постановки задачи. Как математик вы вольны выбрать факторы которые влияют на вашу задачу и параметризировать их или фиксировать. А тут уж извените всё зависит от ваших хотелок и никто вам не в праве запретить разбивать на 4 или на 2 группы или рассмотреть вам все возможные разбиения. Или же поставить как задачу оптимизации разбиения.
                Правильный обед должен состоять из 5 блюд приготовленных из 33 ингредиентов.
                  Pavia, в данном случае мне нужна РЫБА, а НЕ УДОЧКА! ну ты понял о чем я...

                  Цитата Pavia @
                  А у вас всегда так. Шаг в сторону и Вы теряетесь. Что делать если Ваш автор не дал точного описания?

                  тот автор (хотя там была какая-то мини статья) дал мне больше, чем вы...

                  и еще, насчет того, что "хеширование по сигнатуре" - не алгоритм, а научная проблема. Я тупо (подчеркиваю, ТУПО) вбиваю в гугл фразу "Хеширование по сигнатуре" и пошли всякие ссылки, где идет сочетание "алгоритм хеширования по сигнатуре"...
                  хотя я соглашусь, что это больше общее название семейства алгоритмов, а не какого-то конкретно...

                  Добавлено
                  в моем конкретном случае, существует определенный алгоритм, который можно расписать по этапам, четко и без всяких околоалгоритмических рассуждений...знать бы еще как....
                  I originate
                  You must appreciate, all the others imitate

                  SCOOTER "GUEST LIST"

                  'Pon the mic I'm the teacher!
                  Spread my words like a preacher!
                  Yiiihhaaaa!!!!

                  SCOOTER "WEEKEND"
                    Цитата Pavia @
                    Взять компиляторы 60-тых годов там 4 байта для идентификатора.
                    Вообще-то 6. Поэтому имена процедур во многих библиотеках, ведущих историю из тех годов (BLAS, LAPACK, FFTPACK, MINPACK, FITPACK, QUADPACK, ODEPACK), состоят из 5-6 символов.
                    Оттуда же ограничение на длину системных функций POSIX - 5 символов - один символ съедает лидирующее подчёркивание.
                    Всё написанное выше это всего лишь моё мнение, возможно ошибочное.
                      В итоге вот, что у меня получилось!
                      Из примера в статейке понял (возможно, что неправильно), что длина битового ХЕША зависит от длины поискового образца, а не от длины слов в БД.
                      Алгоритм такой:
                      1. Сформировали битовый ХЕШ поискового неточного образца
                      2. Для каждого слова из БД получаем ХЕШ, длина которого строго равна длине ХЕШа поискового образца (разбивка на группы алфавита делается последовательно, с переходом на новый слой)
                      3. Если ХЕШи равны с точностью до 1 бита, то считаем, что слово совпало с образцом.

                      Выводы программы (на СИ):
                      Прикреплённая картинка
                      Прикреплённая картинка


                      Но вообще очень странно видеть, когда слово из БД, считается совпавшим с образцом, типа "ovr" - "hello", или "mgymwjlcobgw" - "hello" :lol: , ну, не знаю..., такое это))
                      Наверняка что-то общее есть в том числе между грузовиком и яблоком...)

                      Скажите, плиз, я сделал ПОЛНЫЙ БРЕД или все хорошо?

                      Скрытый текст
                      Перечень функции программы (СИ):
                      ExpandedWrap disabled
                        // создание файла для теста
                        void CreateFileWords(void)
                        // получение битового хеша для
                        int* GetBitMask(char *ps, int plen)
                        // сравнение двух битовых хешей на равенство
                        // 0 - НЕ равны, 1 - равны
                        int IsHashEqual(int *psample, int *pword, int pn)
                        // неточный поиск
                        void SearchWords(char *psample, int plen, int *pBitMaskSample)
                      I originate
                      You must appreciate, all the others imitate

                      SCOOTER "GUEST LIST"

                      'Pon the mic I'm the teacher!
                      Spread my words like a preacher!
                      Yiiihhaaaa!!!!

                      SCOOTER "WEEKEND"
                        amk
                        В проекте Апполо было 4. У Фортарна 6 у языка Ада 8 байт

                        FasterHarder
                        А что сами не видите что это полный бред?

                        Добавлено
                        "arrow", "xuxbp".

                        Разложили по буквам Вы неправильно, это мелочь.

                        ExpandedWrap disabled
                          a f k p u
                          b g l q v
                          c h m r w
                          d i n s x
                          e j o t y
                                  z

                        Правильно так
                        ExpandedWrap disabled
                          0 1 2 3 4
                          a g m s y
                          b h n t z
                          c i o u  
                          d j p v  
                          e k q w  
                          f l r x


                        Во-вторых кодировали вы тоже неправильно. Правильно так:
                        arrow
                        02223 -> 000 010 010 010 011 -> 00001001 00100110
                        xuxbp
                        33302 -> 011 011 011 000 010 -> 01101101 10000100
                        Сообщение отредактировано: Pavia -
                        Правильный обед должен состоять из 5 блюд приготовленных из 33 ингредиентов.
                          Цитата Pavia @
                          Разложили по буквам Вы неправильно, это мелочь.

                          Ха! Вот давай об этом поговорим. Хоть что-то конкретное и ПОЛЕЗНОЕ будет.
                          Ну, во-первых, я НЕ нашел ни одного абзаца нигде, как нужно раскладывать по буквам.
                          Вот смотри, три варианта, какой верный????????????????????????? А главное, почему?
                          Прикреплённая картинка
                          Прикреплённая картинка


                          И ты приводишь свой вариант:
                          Цитата Pavia @
                          0 1 2 3 4
                          a g m s y
                          b h n t z
                          c i o u
                          d j p v
                          e k q w
                          f l r x


                          если хочешь/можешь, то напиши строгую формализацию этого разложения


                          P.S. не так я по буквам раскладывал, как ты говоришь, на картинке показано как
                          I originate
                          You must appreciate, all the others imitate

                          SCOOTER "GUEST LIST"

                          'Pon the mic I'm the teacher!
                          Spread my words like a preacher!
                          Yiiihhaaaa!!!!

                          SCOOTER "WEEKEND"
                            FasterHarder
                            Цитата FasterHarder @
                            А главное, почему?

                            Почему вы уже сами ответили. Потому что у разных слов получается одинаковый хэш. Хочется наоборот.

                            Цитата FasterHarder @
                            если хочешь/можешь, то напиши строгую формализацию этого разложения

                            Количество букв в алфавите разделить на количество столбцов. Всё как учили во 2-ром классе школы
                            https://interneturok.ru/lesson/matematika/2...po-soderzhaniyu

                            26/5=5,2 округляем в верх получаем по 6 бук в столбце.
                            Строка = (номер_буквы) mod 6
                            Столбец= (номер_буквы) / 6

                            Почему на последнем рисунке через один? Очевидно, что так красивее.

                            Добавлено
                            Если мы перемешаем буквы как попало то мы можем нарушить свойства сравнения.
                            Код(буква1)<Код(буква2) тогда и только когда
                            буква1<буква2

                            Соответственно заполнять мы должны по столбцам. Берём буквы по их порядковым номерам и заполняем столбцы. Заполнили первый переходим ко второму и так далее.

                            Это позволит нам быстро сортировать таблицы из этих хэшей.
                            Сообщение отредактировано: Pavia -
                            Правильный обед должен состоять из 5 блюд приготовленных из 33 ингредиентов.
                              про формализацию не об этом речь! формула заполнения мне не нужна. нужно было доказательство того, что располагаем по колонкам
                              Цитата Pavia @
                              Почему вы уже сами ответили. Потому что у разных слов получается одинаковый хэш. Хочется наоборот.

                              ну и что! мне непонятно.
                              Вообще, поскольку не учитываются орфография слов, абсолютно поровну состав слов и порядок/частотность букв в нем. Не вытекает ли из этого, что буквы в слоях можно вообще располагать ХАОТИЧНО (понятно, что в рамках одного эксперимента он не изменяется), главное равномерное кол-во в колонках/строчках. Вообще не выкупаю этот момент))


                              Цитата Pavia @
                              Очевидно, что так красивее.

                              Кому очевидно...)

                              Цитата Pavia @
                              Это позволит нам быстро сортировать таблицы из этих хэшей.

                              это фраза вгоняет меня в еще более глубокий тупик, уже безвылазный)
                              БЫСТРО? - ок
                              СОРТИРОВАТЬ? - зачем
                              ТАБЛИЦЫ ХЕШЕЙ? - хммм...нет такого здесь) есть ХЕШ поискового образца и ХЕШ текущего проверяемого слова.

                              Кстати, кое-где еще прочитал, что:
                              1. если ХЕШи совпали, то после ЭТОГО делается стандартная проверка строк/слов на равенство и потом уже делается вывод: равны/не равны
                              2. увеличение кол-ва слоев алфавита понижает возникновение коллизий (это я и так понимал). Именно по этой причине я просил ФОРМАЛИЗАЦИЮ расстановки алфавита. Т е тут НЕТ формализации строгой. Мда...Это уже окончательный тупик в понимании происходящего!

                              Ладно, сразу задам все окончательные вопросы. Вдруг, внезапно, у кого-нибудь появится желание рассказать про это (маловероятно!)

                              1. В принципе есть какая-то ХЕШ-функция, которая что-то делает. Имеется в виду, когда расстановка алфавита по колонкам и получение битовой маски. Ок, с большим горем это и непониманием это можно сделать абы как. Но нужна еще одна ХЕШ-функция), которая делает тоже самое, но по-своему. Т е результат одинаковый, а функции различные. Я честно говоря не понимаю, не выкупаю, не знаю, что еще можно тут замутить. Инвертировать биты? Зачем! Нет, 0 мыслей, полный 0 мыслей...никаких шансов это реализовать.
                              2. Затем эти 2 функции (пока непонятно как одну-то сделать) сравнить по эффективности. Ох...
                              Насколько я знаю, фундаментально эффективность оцениваются 2 параметрами:
                              а) затраченное время
                              б) затраченная память
                              По времени: на мое малое ИМХО они будут работать за одно и то же время. Смысл одинаковый. Считать слов из файла. Получить ХЕШ, сравнить. Там нет ничего такого, где бы было повышение/понижение производительности. НЕ ЗНАЮ абсолютно, как можно по времени сравнить. Да одно и то же будет. Единственное, если слова могут быть, например, миллиард символов, то там можно как-то модифицировать/ускорить алгоритм получения битового ХЕШа...или вообще не о том это все.
                              По памяти: вроде тоже полная идентичность. Память для слова, для Хеша. Все. Да одно и то же будет.
                              Как еще эффективность можно сравнить этих ХЕШ-функций? По кол-ву перестановок, сравнений? Но так вроде сортировки сравнивают. Не знаю в общем.
                              Слава б-гу, что не нужно делать оценку сложности, типа O(n) или O(n^2 * m/2), т к там будет какая-то дикая жесть, которую мне НИКОГДА не оценить правильно.
                              Скрытый текст

                              я бы даже заплатил за грамотное, ПОЛНОЕ и доступное объяснение этих моментов, но мои копейки мало кого заинтересуют здесь...)
                              Сообщение отредактировано: FasterHarder -
                              I originate
                              You must appreciate, all the others imitate

                              SCOOTER "GUEST LIST"

                              'Pon the mic I'm the teacher!
                              Spread my words like a preacher!
                              Yiiihhaaaa!!!!

                              SCOOTER "WEEKEND"
                                В общем более-менее разобрался с этим ХС!

                                1. Длина хеша не зависит от длины слов в БД
                                2. Длина хеша не зависит от длины поискового слова
                                3. Длина хеша выбирается анализом (или итерационно меняется для сравнения) в зависимости от мощности алфавита данных слов (в моем примере 26 лат.букв было).
                                4. 1 этап - "индексирование" заданных слов, т е формирование хеш-таблицы, через вычисление сигнатуры. Длину хеша можно брать произвольной, но чем КОРОЧЕ, тем больше коллизий ---> больше мусорных слов в результатах поиска. Это самый времязатратный процесс, т к пока слово считается из файла, вычислится его сигнатура, затем попадет в нужный слот ХТ.
                                От длины хеша зависит сколько будет слоев при вычислении сигнатуры. Если L = 26, то 1 слой, если L = 6, то 5 слоев. При этом расстановка алфавита в слоях НЕ ИМЕЕТ НИКАКОГО ЗНАЧЕНИЯ!!

                                Прикреплённая картинка
                                Прикреплённая картинка


                                Как я понимаю (возможно, здесь неточно) кол-во слотов в ХТ = кол-во различных сигнатур, получающихся при обработке входных слов. Например: если длина хеша = 13, то предельное кол-во слотов в ХТ будет 2^13. В результате образуется дико разряженная ХТ, если кол-во обрабатываемых слов невеликов. Хорошо, когда слов 5лямов, тогда заполняемость (fillfactor) неплохая.
                                5. 2 этап - сам поиск по ХТ. Вводим искомое слово, вычисляем для него сигнатуру, длина которой равна сигнатурам всем словам из БД. Лезем в слот ХТ, имеющий такой же "индекс" и считываем все слова из этого слота. Это неточный поиск, который якобы имеет "0 ошибок". В реальности это не так, если кол-во слоев больше 1. Если слой 1, то ДА, гарантируется такой же состав слова, но не взаимное расположение букв, т е слова "hello" и "olllehhhohhheee" будут иметь одинаковую сигнаутру при любой длине хеша!
                                6. Чтобы найти слова с "1 ошибкой" меняем каждый бит в хеше искомого слова на противопложный и запускаем стандартный поиск. Работает отлично (на малых слоях), на больших результат крайне мусорный, если слоев 3-4 штуки, слова ВООБЩЕ могут быть не похожими по структуре.

                                Минусы, которые я вижу:
                                1. Крайне нерациональное использование памяти для указателей слотов в ХТ. Приходится выделять сразу для всевозможных сигнатур, 2^m, где m может быть очень велико. ХТ может быть крайне разряженной. Худший случай, когда 5лямов одинаковых слов и алфавит, например 52 буквы. Хешируем в 1 слой. Выделяем памяти для слотов в кол-ве 2^52, а все слова падают в один и тот же слот, образуя простой ЛОС. ИМХО, но с этим нужно мириться, т к ПЕРЕСТРАИВАТЬ ХТ, например, расширять ее, хрен знает как + очень может быть долго, если в ней уже содержится много слов.
                                2. Очень мусорный поиск, когда слоев > 2 хотя бы, да даже при 2 слоях результаты оставляют желать лучшего. требуется постобработка какая-то.
                                3. Требуется ПОЛНАЯ перестройка ХТ, когда меняется длина сигнатуры
                                4. Хрен где в сети есть полное описание (чтобы каждый дурак понял) этого алгоритма. Все ссылаются на книгу Бойцова, а это какое-то метод.издание МГУ по выс.мат и информатике, выпущенное в "0" экземпляров. Найти не смог...

                                Краткая сводка теста:
                                кол-во слов 5мил. длина от 2 до 10 символов. Автогенерация. 1слой, т едлина хеша 26бит.
                                Поиск слова "mirrow". 50миллисек для поиска слов "0ошибок" (найдено 13 штук), 120миллисек для "1 ошибка"(289 штук). Построение ХТ около 13 секунд (13 000 миллисекунд)

                                кол-во слов 5мил. длина от 2 до 10 символов. Автогенерация. 2слоя, т едлина хеша 13 бит.
                                Поиск слова "mirrow". 324миллисек для поиска слов "0ошибок" (найдено 701 штук), 4183 миллисек для "1 ошибка"(9702 штук). Построение ХТ около 13.2 секунд (13 200 миллисекунд)

                                Но есть один момент, котоырй вообще непонятен!

                                В теории говорится, что в ХС нужно знать частоту появления каждого символа алфавита.
                                При расчетах выше она принимается равновероятной. Т е появление буквы 'a' = 1/26 (~3.85%), b = 1/26, ..., z = 1/26.
                                Допустим будет оговорено, что вероятность появления букв 'a', 'p', 'o' не 3.85%, а 7.5%, а остальные равнозначны. И ЧТО! как этим воспользоваться? Эти буквы нужно располагать в спец.битах хеша, а нафига! вот это я вообще не понимаю...

                                и пример ф-ции сигнатуры, которая одновременно выступает как ХФ:
                                ExpandedWrap disabled
                                      UInt32 GetHash(String ^pword, const UInt16 plenHash)
                                      {
                                          UInt32 hash = 0;
                                          for(Int32 i = 0; i < pword->Length; i++)
                                          {
                                              UInt32 one = 1;
                                              UInt32 shift = ((int)pword[i] - (int)'a') % plenHash;
                                              one = one << shift;
                                              hash = hash | one;
                                          }
                                          return hash;
                                      }


                                типа UInt32 хватает для битовой сетки в 32 разряда. У меня 26 букв максимум. Все норм. Если бы были еще большие буквы, тогда берем тип UInt64 или типа того...
                                Сообщение отредактировано: FasterHarder -
                                I originate
                                You must appreciate, all the others imitate

                                SCOOTER "GUEST LIST"

                                'Pon the mic I'm the teacher!
                                Spread my words like a preacher!
                                Yiiihhaaaa!!!!

                                SCOOTER "WEEKEND"
                                1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)
                                0 пользователей:


                                Рейтинг@Mail.ru
                                [ Script Execution time: 0,1929 ]   [ 24 queries used ]   [ Generated: 22.05.19, 20:55 GMT ]