Почему данный код для генерации подписи в символьной строке использует хэш по модулю возвращающего символа (0)? - PullRequest
Новая
       34

Почему данный код для генерации подписи в символьной строке использует хэш по модулю возвращающего символа (0)?

0 голосов
/ 25 января 2019

Первая публикация о переполнении, поэтому я заранее извиняюсь, если выхожу из формата.

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

Я работал с расстояниями Левенштейна и JW в качестве метрик для сходства, однако, как и следовало ожидать, их сложность O (n) прямо пропорциональна длине сопоставляемых строк.

Векторизация этих функций расстояния по двум имеющимся у меня символьным векторам будет занимать много памяти и времени, и я ожидаю столкнуться с переполнением буфера.Я попытался запустить алгоритм расстояния на небольшом подмножестве этих векторов, и пространство памяти заняло довольно много.

Поэтому Я решил сгенерировать хэш-подписи каждой строки, чтобы они занимали меньше места и могли обрабатываться быстрее.Алгоритм, который я использовал для генерации того же самого, можно найти здесь: Сверхбыстрая оценка-Левенштейна-Расстояние

В общем, алгоритм выполняет следующие шаги:

  1. Инициализировать массив (я использовал df с оригинальным именем ascii ) печатных символов ASCII для элементов подписи.
  2. Создание хэша текстовых подстрок с использованием значения fov, определяющего длину подстрок.(Я использовал "md5" , должен ли я использовать "xxhash32"; это что-то сильно меняет?)
  3. Вычислить по модулю целочисленного хэша на величину сжатиярешено до реализации.
  4. Если оно не равно нулю, прервите или переключитесь на следующее в цикле.Если это так, верните символ из набора данных ascii как: ascii [( int.hash %% length (ascii) ),]
  5. Loop, пока не достигнетеконец строки.
  6. Вернуть подпись.

Я написал функцию, пытающуюся реализовать то же самое, но она бросает только символ (0) в меня.Некоторая помощь в определении оскорбительного предложения будет принята с благодарностью.

Параметры функции:

  • x : строковый ввод для генерации подписи
  • сжатие : сжатиекоэффициент для сигнатуры
  • fov : длина подстроки, которая будет учитываться на каждой итерации

Я предоставляю код функции и вывод ниже:

Код: 

library(Rmpfr)
library(digest)

  Sigtex <- function(x,compress,fov){  
  x <- as.character(x)  
  compress <- as.integer(compress)  
  fov <- as.integer(fov)  
  s = character()  
  for(i in 1:nchar(x)){  
  modu <- mpfr(x =digest(substr(x,i,(i+fov)), algo = "md5",serialize = F),base = 16)
    if(modu%%compress != 0){
    if(i==nchar(x)) {break} 
    else {next} } 
    else{s = paste(s,ascii[(modu%%62),],sep = "")}}  

    if(i==nchar(x)) {return(s)} 
    else {next} }

Выход: 

  >Sigtex("Simbasrteha",123,3)
  character(0)

  >Sigtex("LionKing",123,5)
  character(0)

Еще раз спасибо.

...