roboforum.ru

Технический форум по робототехнике.

 

Алгоритм мгновенного поиска по БД любого размера

Автомат, адаптивный автомат ... разум

Алгоритм мгновенного поиска по БД любого размера

Сообщение EdGull » 20 авг 2008, 22:31

оригинал статью находится здесь http://aimatrix.nm.ru/aichip/AIProcessors1.htm
Операции поиска

Представим себе некоторый искусственный нервный узел, выполняющий поиск какого-то значения в подведомственной ему памяти. Допустим, у этого узла имеется в наличии память из пяти ячеек, хранящих пять разных поименованных свойств с их числовыми значениями. Пусть имена свойств (ячеек памяти) будут представлять имена пяти членов семьи, а числа в свойствах - возраст каждого члена семьи. Нужно найти возраст человека по имени "Петя". Вот условная схема такого узла.

AIProcessors05.gif
AIProcessors05.gif (8.51 КиБ) Просмотров: 2053


На входной дендрит поискового нейрона ПН передается извне нервный сигнал, в котором закодирована команда, что требуется найти. На языке программирования такая команда понималась бы как "взять значение свойства ПЕТЯ". Поисковый нейрон ретранслирует эту команду в свой аксон, чтобы нейроны памяти Я1, Я2, Я3, Я4 и Я5 могли немедленно приступить к обработке принятой команды. Обратите внимание, как механизм поиска отличается от традиционного программного поиска. Каждая ячейка памяти выполняет поиск самостоятельно, причем для ускорения поиска они все выполняют его синхронно. Ячейка памяти не отзывается, если переданное в команде имя свойства не равно имени ячейки. Отзывается только та ячейка, чье имя совпало с именем свойства. В свой аксон она выдает ответ, который попадает в дендрит поискового нейрона. В итоге поисковый нейрон через свой аксон возвращает наружу (за пределы нервного узла) ответ в виде возраста человека по имени "Петя".

Важная особенность подобных схемных решений памяти в том, что за два такта операции поиска (ретрансляция в аксон команды поиска, подача в аксон нервного паттерна с ответом) находится требуемое значение независимо от объема памяти. Аксон поискового нейрона в нервном узле используется как для ретрансляции команды поиска нейронам памяти, так и для передачи команды ответа наружу. Но тогда обязательно требуется, чтобы наружное окружение, которое запрашивало у нервного узла исполнить операцию поиска, реагировало только на команду ответа, игнорируя прочие команды, пущенные поисковым нейроном в свой аксон и предназначавшиеся для нейронов памяти. Можно, конечно, избавиться от трудности по-другому, установив на выходе дополнительный нейрон, следящий, чтобы на выход нервного узла не попадало ничего, кроме команды ответа. Однако это не скрывает в полной мере проблем типизации сигналов. Даже на скорую руку выясняется, что должны существовать как минимум типы сигналов "запрос исполнения" и "ответ". К тому же первый из них логично снабдить субтипами: какой конкретно запрос - с ответом или без; запрос чего именно - исполнения действия или возврата состояния, и тому подобное. Прибавим сюда и необходимость управленческих типов сигналов: что-то в духе "отбой предыдущего запроса", "временно отложить" и так далее. Не отрицается разумная нужда в сигналах типа "переброс, перемещение, замещение данных", когда связи цепочки нейронов используются просто как транспортные каналы. Сразу возникает потребность в указании источника и получателя. А это ведет к неизбежному структурному устройству нервного паттерна. В общем, проблему типизации предстоит когда-нибудь решить, сейчас же в этой связи приходится больше гадать, чем опираться на какие-нибудь практические знания.

Иерархическая память

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

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

В ходе развития организма в нервной системе создается множество нейронов. У каждого из них имеется достаточно большое количество дендритов. В результате количество контактов дендритов с аксонами других нейронов достигает больших значений. Но не каждый физический контакт обозначает электрическое соединение. У определенного нейрона имеется множество дендритов, и только часть из них "припаяна" к аксонам других нейронов, остальная часть дендритов просто заведена к местам возможных подключений, но не подключена. Если в месте контакта нет нейротрансмиттеров - химических веществ, проводящих нервные сигналы, - никакого контакта не будет. Однако контакт может быть установлен по требованию. В этом случае в области контакта с помощью физико-химических процессов генерируются нейротрансмиттеры, "припаивая" дендрит к аксону. Таким же образом бывшая ячейка памяти получает в личное пользование набор свободных нейронов.

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

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

Дмитрий Сахань, 18 июня 2002 года


Добавлено спустя 18 минут 35 секунд:
так вот, в переводе на язык электронщиков это обычная микросхема памяти с параллельным доступом!
входы это адрессация выход это шина данных
и самое главное никакого тактования!!!
т.е. как только изменятся данные на входах адрессной линии, на выходе шины данных мгновенно появится новое значение
т.е. будет произведен мгновенный поиск значения внезависимости от размера самой памяти!!!
минус как бы тут один, не рациональное использование памяти, т.е. под один вид данных уйдет весь объем микросхемы, хотя при этом никто не запрещает ввести в адресацию старших битов кодировки к какому типу относится данный запрос.

именно для этого в первую очередь я и сделал на миниботе-про SD-card для ассоциативной памяти
ведь технически флеш-память можно расматривать как скучкованную в одном месте гору микросхем отдельных параллельных памятей по 512 байт. В случае с 2ГБ карточкой это 3.967.488 микросхемок по 512б всего за 200р.!!!

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

Добавлено спустя 8 минут 10 секунд:
и самое главное, голосование в распозновании образов я думаю именно так и постоенно...
Аватара пользователя
EdGull
 
Сообщения: 10211
Зарегистрирован: 28 дек 2004, 20:33
Откуда: Тольятти
Skype: Ed_Gull
прог. языки: Bascom AVR Basic
ФИО: Гуль Эдуард Викторович

Re: Алгоритм мгновенного поиска по БД любого размера

Сообщение avr123.nm.ru » 20 авг 2008, 22:47

ИМХО статья БРЕДЯТИНА. Точно так же поиск в обычных МК системах - куча устройств на шине i2c например а откликается только то которое спрашивали. Умных слов накидали :cry: нейроны, аксоны :o
Аватара пользователя
avr123.nm.ru
отсылающий читать курс
 
Сообщения: 14200
Зарегистрирован: 06 ноя 2005, 04:18
Откуда: Москва
Предупреждения: -8

Re: Алгоритм мгновенного поиска по БД любого размера

Сообщение Ku6opr » 21 авг 2008, 01:28

Какое устройство сможет выполнять параллельную обработку нейронов, чтобы обеспечить преимущество?

входы это адрессация
Каким образом вы будете кодировать строки (или ключ), чтобы бесконечное количество различных строк не создавало коллизии? Имхо, получается обычная HashTable

куча устройств на шине i2c например а откликается только то которое спрашивали
количество устройств будет линейно рости с увеличением запомненных объектов, так что использовать такую систему можно только для "пяти членов семьи" :D
Аватара пользователя
Ku6opr
 
Сообщения: 50
Зарегистрирован: 19 май 2008, 12:04
Откуда: Украина, г. Харьков
прог. языки: C#, C++

Re: Алгоритм мгновенного поиска по БД любого размера

Сообщение EdGull » 21 авг 2008, 06:42

1. обычно в БД поля имеют фиксированное значение
2. не забываем что у нас "специализированная БД"

и так, отводим под поле "имя" допустим 10 байт, значит нам нужна память с 80-ти разрядной адресной шиной...

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

или допустим нам надо посчитать колчилество еденичек т.е. система голосования, допустим от 40-ка "нейровнов", берем память с 40-ка разрядной адресной шиной...

дальше понятно?

это принцип ассоциативной памяти, т.е. памяти ("нейрону") пофигу какие распозновать образы подаваемые на входа!
то ли это будут сигналы с дачиков звука, видео или запахов...

т.е. подали комбинацию на вход, если все нули, то следующий "слой" кричит наружу, не знаю такого образа, ему дают команду "передай памяти, что это образ номер такой-то или того-то"

Добавлено спустя 1 минуту 50 секунд:
Какое устройство сможет выполнять параллельную обработку нейронов, чтобы обеспечить преимущество?

ЛЮБАЯ ПЛИС с рождения работает параллельно.
Аватара пользователя
EdGull
 
Сообщения: 10211
Зарегистрирован: 28 дек 2004, 20:33
Откуда: Тольятти
Skype: Ed_Gull
прог. языки: Bascom AVR Basic
ФИО: Гуль Эдуард Викторович

Re: Алгоритм мгновенного поиска по БД любого размера

Сообщение frig » 21 авг 2008, 09:04

описанное в статье обычная память. мы отдаем адрес ячейки - получаем её значение. а теперь давайте попробуем обратную операцию. нам надобно найти адреса ячеек с определенными значениями.. каким макаром?

1. обычно в БД поля имеют фиксированное значение


верно. только полей этих более одного, и операция выборки значения поля по его адресу - самая примитивная.
давайте попробуем определиться с более реальными задачами.. таблица с 3-мя полями. имя, возраст, рост. надобно выбрать возраст людей с ростом более 160см.
как там наша замечательная БД должна отработать? какой ширины должна быть шина адреса? :-))

ИМХО статья БРЕДЯТИНА.


мне чего-то тоже так показалось...
frig
 
Сообщения: 1640
Зарегистрирован: 12 фев 2007, 12:25
Откуда: Днепр

Re: Алгоритм мгновенного поиска по БД любого размера

Сообщение Виталий » 21 авг 2008, 11:11

Описанное выше - обычный хеш.
А теперь объясни с какой стороны такая мгновенность может быть полезна? Если в системе распознавания, то там нет такой задачи т.к. количество образов невелико и с ним справиться любая "обычная" программа, никаких плис там не надо. То же самое с системой голосования. Основная нагрузка на обработку изображения.
Все новости о моих проектах http://savethebest.ru
Аватара пользователя
Виталий
 
Сообщения: 2114
Зарегистрирован: 08 окт 2004, 16:43
Откуда: St. Petersburg
Skype: quark-bot
ФИО: Клебан Виталий

Re: Алгоритм мгновенного поиска по БД любого размера

Сообщение Digit » 21 авг 2008, 11:24

Согласен со всеми выше отписавшимися - бредовастенько и ничего нового
злой полицейский
Аватара пользователя
Digit
 
Сообщения: 3339
Зарегистрирован: 27 ноя 2004, 00:42
Откуда: совсем Москва
ФИО: Григорий

Re: Алгоритм мгновенного поиска по БД любого размера

Сообщение EdGull » 21 авг 2008, 11:34

вот сразу видно ваше обремененное знанием сознание... :D
ну тогда давайте посчитаем сколько вам нужно тактов чтобы посдчитать кол-во еденичек в допустим 64 битном слове... :wink:
Аватара пользователя
EdGull
 
Сообщения: 10211
Зарегистрирован: 28 дек 2004, 20:33
Откуда: Тольятти
Skype: Ed_Gull
прог. языки: Bascom AVR Basic
ФИО: Гуль Эдуард Викторович

Re: Алгоритм мгновенного поиска по БД любого размера

Сообщение sash13 » 21 авг 2008, 11:49

О ужас :o
sash13
 
Сообщения: 114
Зарегистрирован: 10 фев 2008, 00:29
Откуда: Киев Украина
прог. языки: php C++ MIDI 0_o

Re: Алгоритм мгновенного поиска по БД любого размера

Сообщение Виталий » 21 авг 2008, 11:59

Давайте...
Пускай у меня будет 2000 тактов, а у тебя 1. Вопрос в другом. Голосование производится не больше 30 раз в секунду. Чаще не надо. Если у меня это будет занимать 2000 тактов, а у тебя 1, то это совершенно не играет никакой роли, т.к. я тоже буду успевать.

Я предлагаю посчитать сколько памяти необходимо чтобы запомнить количество единичек для каждого из 2^64 чисел. Если по одному байту на одно чило, то это всего-навсего 16 зеттабайт.

Добавлено спустя 1 минуту 22 секунды:
Для справки зетта - 10^21

Добавлено спустя 4 минуты 26 секунд:
Это 87960930223 винчестера по 200Гб, при средней скорости доступа в 5мс к любому винчестеру (это будет очень круто) время поиска в худшем случае ~14 лет.
Ну без ухищрений конечно.
Все новости о моих проектах http://savethebest.ru
Аватара пользователя
Виталий
 
Сообщения: 2114
Зарегистрирован: 08 окт 2004, 16:43
Откуда: St. Petersburg
Skype: quark-bot
ФИО: Клебан Виталий

Re: Алгоритм мгновенного поиска по БД любого размера

Сообщение EdGull » 21 авг 2008, 12:12

ну хорошо... :D
для понимания упростим, 20 бит адрессной шины, 8 бит данные = 1 мегабайт
согласен?
сколько тактов у тебя удет на посчет 20 еденичек?
Аватара пользователя
EdGull
 
Сообщения: 10211
Зарегистрирован: 28 дек 2004, 20:33
Откуда: Тольятти
Skype: Ed_Gull
прог. языки: Bascom AVR Basic
ФИО: Гуль Эдуард Викторович

Re: Алгоритм мгновенного поиска по БД любого размера

Сообщение Виталий » 21 авг 2008, 12:36

При прямом подсчете 19 RISC команд. Что фактически 19 тактов.
При использовании таблицы 4 RISC команды.

Добавлено спустя 2 минуты 32 секунды:
Для 64 бит 64 сдвигф вправо и 64 вычитания, а не 14 лет.
Все новости о моих проектах http://savethebest.ru
Аватара пользователя
Виталий
 
Сообщения: 2114
Зарегистрирован: 08 окт 2004, 16:43
Откуда: St. Petersburg
Skype: quark-bot
ФИО: Клебан Виталий

Re: Алгоритм мгновенного поиска по БД любого размера

Сообщение EdGull » 21 авг 2008, 13:02

ага... то-то я смотрю у всех с последовательными RISC командами получается на ходу всё распозновать образы... :wink:

я это всё к тому что в некоторых случаях есть альтернатива последовательным операциям...
Аватара пользователя
EdGull
 
Сообщения: 10211
Зарегистрирован: 28 дек 2004, 20:33
Откуда: Тольятти
Skype: Ed_Gull
прог. языки: Bascom AVR Basic
ФИО: Гуль Эдуард Викторович

Re: Алгоритм мгновенного поиска по БД любого размера

Сообщение Виталий » 21 авг 2008, 13:47

Я уже написал на что ложиться основная нагрузка, так что я думаю стоит признать, что приведенная архитектура будет иметь выигрыш в очень ограниченном числе вариантов.
Я бы предложил подумать над аппаратом который бы складывал в память очищенное от шумов изображение, контуры и изображения в разных масштабах. Кстати приведенный в соседней ветке про распознавание алгоритм выделения краев основывается на такой операции как "свертка" и известен под названием RobertsCross, возможно немного расширенный. Описанный алгоритм не является оптимальным и может быть существенно расширен.

Добавлено спустя 31 минуту 49 секунд:
ага... то-то я смотрю у всех с последовательными RISC командами получается на ходу всё распозновать образы...

То-то я смотрю на параллельных особо много распознали. =)
Все новости о моих проектах http://savethebest.ru
Аватара пользователя
Виталий
 
Сообщения: 2114
Зарегистрирован: 08 окт 2004, 16:43
Откуда: St. Petersburg
Skype: quark-bot
ФИО: Клебан Виталий

Re: Алгоритм мгновенного поиска по БД любого размера

Сообщение EdGull » 21 авг 2008, 14:11

1. а я сразу писал что это не для всех случаев.
2. насколко я знаю всё кодирование для ют как раз на ПЛИСах... :wink:
Аватара пользователя
EdGull
 
Сообщения: 10211
Зарегистрирован: 28 дек 2004, 20:33
Откуда: Тольятти
Skype: Ed_Gull
прог. языки: Bascom AVR Basic
ФИО: Гуль Эдуард Викторович

След.

Вернуться в Алгоритмы

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1

cron
Mail.ru counter