Я не понял, ты уже отказался от своей формулы? Или она правильная, но к ней нужна еще одна формула для вторичного преобразования? Если так, то что из себя представляет вторая формула?

Ну я тоже брал логарифм по основанию 2, чтобы вручную не считать количество двоичных символов в слове "шарпер". И ведь не просто попытался, а взял, между прочим.

По твоей формуле уже 33^4 больше миллиона, так что 20 бит хватит только для записи уникального кодового номера слова не длиннее 3 букв. Заметь, не всех 3-буквенных слов, а только одного. Ну в принципе, понятно что это слово *срабатывание гусар-контроля*
И слово "шарпер" никак в 20 бит не влезет.

Каких еще дубликатов? Уникальных слов будет строго равное количество хоть в символьном виде, хоть в виде десятичного кода, хоть в двоичке. Символьное перекодирование никак не влияет на число уникальных слов. Точнее даже так: если в результате перекодирования число уникальных слов уменьшается, то это является прямым признаком коллизий, то есть некорректной работы алгоритма перекодировки.
Ну, в принципе, Лукомор эту проблему уже описал. Можно свести все слова к однобитной записи, так что слов в словаре окажется столько же, сколько и букв в алфавите, то есть два. Это существенная экономия памяти, да. Теряюсь в догадках - почему никто этот алгоритм для поиска не использует до сих пор?

Ой, ну будет у тебя ник не Шарпер, а Шарпец, делов то.

Логарифм не выдаст, свинья не съест.

Как здесь избежать поворения фамилии "Иванов", имени "Иван", отчества "Иваныч"?
И повторения корня слова "штан"?

Отредактировано Лукомор (2022-01-25 08:10:08)

Без понятия. Вопрос мой простой: мы по прежнему обсуждаем формулу КС+33*(ПС+33*(ПС+(33*НС))) или уже что-то другое?

Пока что смущает только то, что это преобразование не было описано.

И то, что в 20 бит нельзя записать числовой код для одного слова длиннее 3 букв.

Я правильно понимаю, что ник "Шарпер" записывается не как символьная последовательность "Шарпер" и не как числовой код 1019371734, а в виде номера слова? Ну, например, если смотреть на список участников форума, то номер 3.
Если да, то еще раз спрашиваю - что мешает присвоить этот номер самому слову "Шарпер" без преобразования в числовой код?

Щас! Ты как будто никогда не жил в СССР и никогда не слышал от АТС сообщения о том, что домашний телефон тебе нельзя установить, потому что нет свободных номеров.

Ты о чем вообще? Я пишу про уникальные слова, то есть как раз про то, что остаётся после фильтрации дубликатов.

То-есть, выражения
"Иван Иваныч Иванов",
и
"Иванов Иван Иваныч"

Прочертят одинаковый маршрут в Trie,
а, будучи подставлены в формулу, дадут одно и то же число?

Я все правильно понимаю?

Или, укажи конкретно, какая часть одного и другого выражения будут общей для обоих выражений?

Ну и как в телефонном справочнике обойтись без повторения дубликатов?

Давай без болтовни. Вот есть просто длинный код 1019371734. Как его преобразовать без потери точности в более короткий вид, чтобы на его хранение ушло меньше места? Логарифмы не канают - там чтобы не потерять точность и избежать коллизий, значащих цифр точно не меньше надо хранить.

Чего непонятного то? Для хранения десятичного числового кода слова "шарпер" в двоичном виде нужно 30 битов. В 20 оно никак не влезет.

А это из чего следует? В символьной кодировке слова "шарпер" процессор делает 6 операций по сравнению символов, в двоичном виде ему нужно будет сделать 30 операций по сравнению битов. Пусть даже биты идут побайтно, по 8 штук, тогда будет около 4 операций, но сюда еще плюсуем операции на кодирование. Я пока что вообще никакого уменьшения сложности не вижу, не говоря уж о порядках.

Не рассказывайте сказки. Мне в 1990-е под этим предлогом не ставили телефон.

Это какая-то очень частная постановка задачи поиска. Для работы с текстом "Войны и мира" всё равно нужно хранить весь текст целиком. А считать уникальные слова... а зачем вообще?

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

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

Ага.
У Иванова Ивана Иваныча штук пятьдесят номеров телефонов в справочнике.
Звони по любому - не ошибешься!

Если бы понимал как это сделать, то объяснил бы без проблем.

А чего там проверять?
Логарифм десятичного кода 1019371734 по основанию 2 равен 29,925033109. В первом случае 10 значащих цифр, во втором 11.
Можно эти 11 сократить до 10? Да легко! Логарифм округляется до 29,92503311 и на выходе получаем десятичный код 1019371735, то есть слово "шарпес" вместо "шарпер".
Но нам же много 10 значащих цифр. Нам же надо меньше, чем в десятичной записи. Давайте сделаем 9. Получаем 29,9250331 -> 1019371728 -> "шарпек". Жаль, что одной циферки не хватило, а так бы вообще "шарпей" получилось бы.
Итого, имеем, что логарифмирование пожалуй что увеличивает объем хранения, а не уменьшает. Плюс добавляет риск возникновения ошибки при обратной перекодировке.

Ну, Лукомор уже справился. И что? Предлагается хранить в 20 битах не сами числа, а их порядковые номера? А сами числа и информацию по их связи с порядковыми номерами нужно хранить или номеров хватит?

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

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

Теперь вся надежда на формулу. Берем слова "шарпер" и "шарпе" (можно взять "штаны" и "подштанники", конечно, но честно - лень считать, итог то тот же). Этим словам соответствуют десятичные коды по формуле Шарпера 1019371734 и 30890052 соответственно. Вот глядя на буквы, я даже без таблицы и метода Trie догадываюсь, что можно отфильтровать дублирование фрагмента "шарпе". А вот глядя на цифры, мне даже в голову не приходит, что там есть какое-то дублирование, там вроде ни одной общей пары цифр нету даже.
Ах да, я же забыл, там же логарифмы. Ну ок, для логарифмов по основанию 2 имеем 29,925033109 и 24,880638964. Тоже не очень с фильтрацией дублирований.
Ок, перенумеруем по величине. Получаем 2 и 1. Фильтрация дублей опять идет не так хорошо, как хотелось бы.

А теперь применим последний животворящий приём и поговорим про идентификацию корней, приставок и суффиксов в числе 1019371734. Ну или про идентификацию корней, приставок и суффиксов в слове номер 2, на твой выбор.
Весь - внимание! 

Отредактировано Zagar (2022-01-25 20:26:58)