Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > LISP > индексация триплетов

Автор: whiteman 12.4.2009, 21:25

Друзья,

недавно начал осваивать лисп и мне нужен совет

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

спасибо.

Автор: adejneka 13.4.2009, 05:43

Для какого языка всё делается и какова доля "проидексированных" триплетов? Нужно ли знать, входит ли триплет в набор, или нужно запоминать еще дополнительную информацию?

Если для русского языка, регистр значения не имеет, то всего триплетов (* 33 33 33)=>35937, т.е. запоминать нужно почти каждый второй из возможных. Если нужен определять только наличие, то я бы просто сделал битовый вектор, в котором каждому триплету соответствует позиция (((номер первой буквы)*33+(номер второй буквы))*33+(номер третьей буквы)) (всего 4,5 К). Если нужна дополнительная информация - вектор, но не битовый (144 К на 32-битной машине + объём дополнительной информации).

Если множество триплетов разреженное, то можно использовать хэш-таблицу или

Код


(defstruct dictionary
  (letters "" :type string)
  (values #() :type vector #| of dictionary on levels 1, 2 / of additional info|#))

Тогда словарь ("abc" -> X, "abd" -> Y, "acf" -> Z) можно представить как

Код


#S(DICTIONARY :LETTERS "a"
              :VALUES #(#S(DICTIONARY :LETTERS "bc"
                                      :VALUES #(#S(DICTIONARY :LETTERS "cd" :VALUES #(X Y))
                                                #S(DICTIONARY :LETTERS "f" :VALUES #(Z))))))

Автор: whiteman 13.4.2009, 11:06

adejneka,

большое спасибо за ответ.

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

Я стараюсь написать простой спелчекер, один из способов выявление ошибки - поиск не встречающихся в большом объеме текста триплетов.

Множество триплетов разреженное, язык русский, регистр значения не имеет.

Автор: whiteman 13.4.2009, 14:07

а может имеет смысл триплеты перевести в символы и работать с символами?

Автор: whiteman 13.4.2009, 21:18

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

привожу его код под двум причинам:
1) может кто-то покритикует.
2) может кому-то пригодится.

Код


(defvar *triplets-table* (make-hash-table :test 'equal :size 40000))

(defun add-triplet (atriplet)
  (setf (gethash atriplet *triplets-table*)    T )
)

(defun get-triplet (atriplet)
  (gethash atriplet *triplets-table*)
)

(defun split-3(astring)
"splits input into triplets"
(let (
       (result '())
       (tmpStr)
     )

   (dotimes (i (- (length astring) 2))
     (setq tmpStr (subseq astring i (+ i 3)))
     (if (NOT (search " " tmpStr))
         (progn
           (setq result  (cons tmpStr result ))
           (add-triplet tmpStr)
         )
     )
   )
   result
)
)

Автор: adejneka 13.4.2009, 21:50

Код


(defun split-3 (astring)
  "splits input into triplets"
  (let ((result '()))
    (dotimes (i (- (length astring) 2))
      (let ((tmpStr (subseq astring i (+ i 3))))
        (unless (find #\Space tmpStr)
          (push tmpStr result)
          (add-triplet tmpStr))))
    result))

Можно было еще соптимизировать: поменять местами SUBSEQ и UNLESS-FIND, за счёт чего устраняется создание строки с пробелом:

Код


      (unless (find #\Space astring :start i :end (+ i 3))
        (let ((tmpStr (subseq astring i (+ i 3))))
          (push tmpStr result)
          (add-triplet tmpStr)))

но вряд ли эффект будет заметен.

Автор: whiteman 14.4.2009, 19:14

adejneka, большое спасибо за помощь.