ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Java [игнор отключен] [закрыт для гостей] / Алгоритм поиска наличия слов, содержащих буквы другого алфавита
25 сообщений из 32, страница 1 из 2
  1  все
Алгоритм поиска наличия слов, содержащих буквы другого алфавита
    #39279731
just_vladimir
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
just_vladimir
Участник
Столкнулся с задачкой, с ходу не знаю с какого места подступиться, так что интересуют ключевые слова (может названия каких либо общеизвестных алгоритмов, которые я видимо не знаю) по которым гуглить и т.д. Какие-нибудь предложения алгоритмов по наитию тоже приветствуются.
Есть некое множество текстов, каждый текст состоит из некого набора токенов, в качестве токенов могут быть русские слова, английские слова и просто наборы слитно набранных букв и цифр. И среди всех этих текстов необходимо найти такие тексты, в которых есть русские слова, при наборе которых использовались латинские символы, похожие на кириллические (х - x, о - o, р - p, с - c, т - T, к - k и так далее).
...
Рейтинг: 0 / 0
25.07.2016, 14:58
| Ответить | Цитировать | Написать  
Алгоритм поиска наличия слов, содержащих буквы другого алфавита
    #39279732
just_vladimir
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
just_vladimir
Участник
Если вдруг есть какие-нибудь классные библиотеки в этой области, то ссылки на них тоже приветствуются.
...
Рейтинг: 0 / 0
25.07.2016, 15:00
| Ответить | Цитировать | Написать  
Алгоритм поиска наличия слов, содержащих буквы другого алфавита
    #39279746
just_vladimir
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
just_vladimir
Участник
Фразу разбили на токены, оставили только те токены, в которых одновременно используются кириллические и латинские символы, а вот дальше вопрос, как отличить случайных набор букв от реального слова, на сколько понимаю только по словарю? То есть пытаемся заменить все символы по таблице подстановок и пытаемся найти получившееся слово в словаре, с учетом возможной морфологии?
...
Рейтинг: 0 / 0
25.07.2016, 15:08
| Ответить | Цитировать | Написать  
Алгоритм поиска наличия слов, содержащих буквы другого алфавита
    #39279751
Фотография Blazkowicz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Blazkowicz
Участник
Ключевое слово homoglyph
...
Рейтинг: 0 / 0
25.07.2016, 15:11
| Ответить | Цитировать | Написать  
Алгоритм поиска наличия слов, содержащих буквы другого алфавита
    #39279753
Фотография Blazkowicz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Blazkowicz
Участник
just_vladimir,

Можно использовать какую-нибудь БД похожих символов для нормализации текста
http://stackoverflow.com/a/28304327
http://www.unicode.org/Public/security/latest/confusables.txt
...
Рейтинг: 0 / 0
25.07.2016, 15:14
| Ответить | Цитировать | Написать  
Алгоритм поиска наличия слов, содержащих буквы другого алфавита
    #39279775
just_vladimir
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
just_vladimir
Участник
Blazkowicz,
Спасибо!
...
Рейтинг: 0 / 0
25.07.2016, 15:39
| Ответить | Цитировать | Написать  
Алгоритм поиска наличия слов, содержащих буквы другого алфавита
    #39279872
Atum1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Atum1
Участник
just_vladimir,

а какие объемы ?

можно взять спарк и мапредьюз хадуб. ...и анализировать ...


можно просто смотреть коды символов что русские != английским т.е выподают номера из алфафита (например сумма букв больше итд),

можно стоить можель на основе solr и учитывать словарь в котором люди делают ошибки ... так построены многие поисковики на сайтах
...
Рейтинг: 0 / 0
25.07.2016, 18:42
| Ответить | Цитировать | Написать  
Алгоритм поиска наличия слов, содержащих буквы другого алфавита
    #39279916
just_vladimir
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
just_vladimir
Участник
Atum1,
объемы приличные, но никакие хадупы не нужны, да и это дело десятое, главное алгоритм правильный подобрать.
Про коды символов, имхо, перегиб, я думаю что-нибудь регулярное хорошо подойдет для этих целей.
Словарь с ошибками не очень канает, т.к. в моем случае ищутся не ошибки, а злонамеренное искажение текста, с целью сокрытия информации в поиске, заранее сложно угадать в каком слове это будет делаться.
...
Рейтинг: 0 / 0
25.07.2016, 20:22
| Ответить | Цитировать | Написать  
Алгоритм поиска наличия слов, содержащих буквы другого алфавита
    #39279956
Atum1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Atum1
Участник
just_vladimirAtum1,
объемы приличные, но никакие хадупы не нужны, да и это дело десятое, главное алгоритм правильный подобрать.
Про коды символов, имхо, перегиб, я думаю что-нибудь регулярное хорошо подойдет для этих целей.
Словарь с ошибками не очень канает, т.к. в моем случае ищутся не ошибки, а злонамеренное искажение текста, с целью сокрытия информации в поиске, заранее сложно угадать в каком слове это будет делаться.

По поводу Хадупа и Спарка я имел ввиду такой подход - тем более если у вас большое данные

YouTube Video
YouTube Video
...
Рейтинг: 0 / 0
25.07.2016, 21:50
| Ответить | Цитировать | Написать  
Алгоритм поиска наличия слов, содержащих буквы другого алфавита
    #39279958
Atum1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Atum1
Участник
тут про идею стопслов

https://drupalize.me/blog/201508/configure-search-api-solr-use-stopwords-when-indexing-content
...
Рейтинг: 0 / 0
25.07.2016, 21:55
| Ответить | Цитировать | Написать  
Алгоритм поиска наличия слов, содержащих буквы другого алфавита
    #39279959
Atum1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Atum1
Участник
https://wiki.apache.org/solr/LanguageAnalysis#Stopwords
...
Рейтинг: 0 / 0
25.07.2016, 21:56
| Ответить | Цитировать | Написать  
Алгоритм поиска наличия слов, содержащих буквы другого алфавита
    #39279963
Atum1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Atum1
Участник
вот вам живой пример работы solr с учетом ошибки в запросе
http://www.ntv.ru/finder/?keytext=???????????&sort=PUBLISH_TIME

http://www.ntv.ru/finder/?keytext=????????????&sort=PUBLISH_TIME

158 документов с учетом ошибки и без ...

поиск по 1 млн новостей за все время существования сайта за ms
...
Рейтинг: 0 / 0
25.07.2016, 22:07
| Ответить | Цитировать | Написать  
Алгоритм поиска наличия слов, содержащих буквы другого алфавита
    #39280016
just_vladimir
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
just_vladimir
Участник
Atum1,
данные большие, но это не хадуп, если взять с очень большим запасом, то пусть будет 10 млн текстов по 1КБ в день, это нужно с процессить до 10ГБ в день, все лежит на одном сервере и профит от растаскивания на кластер быстрее перекроется оверхедом на сетевые упражнения, да и нет у меня этого кластера :)

За ссылки спасибо!

ЗЫ: не на органы, но догадка близкая ))
...
Рейтинг: 0 / 0
26.07.2016, 06:59
| Ответить | Цитировать | Написать  
Алгоритм поиска наличия слов, содержащих буквы другого алфавита
    #39280436
Atum1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Atum1
Участник
just_vladimirAtum1,
данные большие, но это не хадуп, если взять с очень большим запасом, то пусть будет 10 млн текстов по 1КБ в день, это нужно с процессить до 10ГБ в день, все лежит на одном сервере и профит от растаскивания на кластер быстрее перекроется оверхедом на сетевые упражнения, да и нет у меня этого кластера :)

За ссылки спасибо!

ЗЫ: не на органы, но догадка близкая ))

ну можно просто взять spark :) тем более что задачка интересная - и тут его можно применить :) даже на одной машине .
...
Рейтинг: 0 / 0
26.07.2016, 15:30
| Ответить | Цитировать | Написать  
Алгоритм поиска наличия слов, содержащих буквы другого алфавита
    #39280635
Фотография Usman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Usman
Участник
just_vladimirкак отличить случайных набор букв от реального слова, на сколько понимаю только по словарю? https://ru.wikipedia.org/wiki/Расстояние_Левенштейна
...
Рейтинг: 0 / 0
26.07.2016, 19:25
| Ответить | Цитировать | Написать  
Алгоритм поиска наличия слов, содержащих буквы другого алфавита
    #39280661
just_vladimir
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
just_vladimir
Участник
Usman,
если заранее знать, какое должно быть слово, то да, edit distance это то что нужно, но я заранее какое это слово не знаю. Думаю без словаря никак.
...
Рейтинг: 0 / 0
26.07.2016, 20:41
| Ответить | Цитировать | Написать  
Алгоритм поиска наличия слов, содержащих буквы другого алфавита
    #39280674
Atum1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Atum1
Участник
just_vladimirUsman,
если заранее знать, какое должно быть слово, то да, edit distance это то что нужно, но я заранее какое это слово не знаю. Думаю без словаря никак.

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

не как алгоритм а как идея :

http://ideone.com/inJQjW в слове есть русские буквы ... они попали вконец массива

Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
import java.text.Collator;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Locale;

public class Test
{
  public static void main(String[] args)
  {
    Collator collator = Collator.getInstance(new Locale("fr", "FR"));
    String original = "éDedCBcхаАХbAàa";
    String[] split = original.split("");
    Arrays.sort(split, collator);
    String sorted = "";
    for (int i = 0; i < split.length; i++)
    {
      sorted += split[i];
    }
    System.out.println(sorted); // "&#233;DedCBcхаАХbA&#224;a"
  }
}
...
Рейтинг: 0 / 0
26.07.2016, 21:21
| Ответить | Цитировать | Написать  
Алгоритм поиска наличия слов, содержащих буквы другого алфавита
    #39280709
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
just_vladimir, ты бы хоть парочку модульных тестов написал. Зачем мучаешь нас и заставляешь
за тебя придумывать кейсы из твоей предметной области?
...
Рейтинг: 0 / 0
26.07.2016, 23:43
| Ответить | Цитировать | Написать  
Алгоритм поиска наличия слов, содержащих буквы другого алфавита
    #39281629
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сергей Арсеньев
Участник
just_vladimirКакие-нибудь предложения алгоритмов по наитию тоже приветствуются.
Решение задачи "в лоб" (требует много памяти под словарь).
Берем словарь русского языка. Строим из него словарь слов с неправильными буквaами. (Слова из чисто русских букв откидываем)
Дальше бьем любой текст на слова и проверяем по "словарю неправильных букв". (дерево или хеш на усмотрение автора).

Или при разбитии на слова проверяем наличие букв двух алфавитов. Если такое есть, то приводим к русскому, если успешно проверяем по словарю русских слов.
...
Рейтинг: 0 / 0
28.07.2016, 08:39
| Ответить | Цитировать | Написать  
Алгоритм поиска наличия слов, содержащих буквы другого алфавита
    #39281635
Фотография Blazkowicz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Blazkowicz
Участник
Сергей Арсеньев Решение задачи "в лоб" (требует много памяти под словарь).
По-моему просто нужно построить индекс, при этом нормализуя слова перед индексацией. Таким образом память под конвертацию текста выделять особо не нужно.
...
Рейтинг: 0 / 0
28.07.2016, 08:45
| Ответить | Цитировать | Написать  
Алгоритм поиска наличия слов, содержащих буквы другого алфавита
    #39281638
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сергей Арсеньев
Участник
Сергей Арсеньев,

Точнее, во втором случае нужна маска из трех битов. Младший - русский, Средний - латиница, Старший - все остальное. Если по приходу на разделитель маска равна 011 - то запускаем проверку слова (можно в отдельном потоке :) ) сбрасываем маску и переходим дальше.

Сложность может возникнуть со словом "co" и ему подобными (целиком из английских букв).
Тут, может быть, нужно анализировать предложение.
...
Рейтинг: 0 / 0
28.07.2016, 08:56
| Ответить | Цитировать | Написать  
Алгоритм поиска наличия слов, содержащих буквы другого алфавита
    #39281640
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сергей Арсеньев
Участник
BlazkowiczПо-моему просто нужно построить индекс, при этом денормализуя слова перед индексацией. тогда BlazkowiczТаким образом память под конвертацию текста выделять особо не нужно.
Задача же найти неправильно набитые слова. Правда словарь может оказаться большой. Предварительная проверка на наличие букв обоих алфавитов (при отсутствии третьих символов, как-тo отдельно обрабатывая "-" и т.п.) может сократить время, при малом проценте "неправильных слов".
...
Рейтинг: 0 / 0
28.07.2016, 09:01
| Ответить | Цитировать | Написать  
Алгоритм поиска наличия слов, содержащих буквы другого алфавита
    #39281647
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сергей Арсеньев
Участник
IBMовцы, чтоб не заморачивать себе голову подобными задачами, даже EBCDIC придумывали. :)
...
Рейтинг: 0 / 0
28.07.2016, 09:08
| Ответить | Цитировать | Написать  
Алгоритм поиска наличия слов, содержащих буквы другого алфавита
    #39281790
Atum1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Atum1
Участник
Сергей Арсеньев,

ну а кто мешает на русском писать с ошибками ? теже слова ? или пропуская гласные?
...
Рейтинг: 0 / 0
28.07.2016, 12:15
| Ответить | Цитировать | Написать  
Алгоритм поиска наличия слов, содержащих буквы другого алфавита
    #39281858
just_vladimir
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
just_vladimir
Участник
Сергей АрсеньевИли при разбитии на слова проверяем наличие букв двух алфавитов. Если такое есть, то приводим к русскому, если успешно проверяем по словарю русских слов.
Примерно по такому варианту я и пошел, только после стадии "приводим к русскому" нужна стадия приведения слова в нормальную форму, а потом уже лезть в словарь, либо нужно иметь словарь со всеми возможными словоформами, тоже вариант.
...
Рейтинг: 0 / 0
28.07.2016, 13:13
| Ответить | Цитировать | Написать  
25 сообщений из 32, страница 1 из 2
  1  все
Форумы / Java [игнор отключен] [закрыт для гостей] / Алгоритм поиска наличия слов, содержащих буквы другого алфавита
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=59&msg=39279956&tid=2123861]:
 0ms
get settings:
 9ms
get forum list:
 13ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 115ms
get topic data:
 11ms
get forum data:
 3ms
get page messages:
 61ms
get tp. blocked users:
 2ms
others: 274ms
total:  494ms
созд. / загр.: 494ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]