У меня 3,4 млн строк в некоторых несколько первых строк повторяются дважды, то есть:
с1 с2 с3 с1 с2 с3 с4 с5 с6 с7 с8 с9
с1 с2 с3 с4 с5 с6
с1 с2 с1 с2 с3
Я думаю надо такой алгоритм:
---
делю строку на слова, загоняю слова в массив, количество слов делю надвое.
Цикл начинается с 2, не более половины количества слов.
Взял первые два элемента массива, сравнил их с следующими двумя элементами.
Если совпадение, то первые два элемента отбрасываю, выхожу из цикла.
Иначе продолжаю поиск в цикле, (беру три элемента массива и так далее до половины).
---
Алгоритм работы мне кажется жутко неэффективным, посоветуйте, пожалуйста, лучший вариант.
Алгоритм поиска повторов в начале строки
Модератор: Модераторы
azsx писал(а): посоветуйте, пожалуйста, лучший вариант.
Проверяйте на повторное вхождение слов, набранный массив - ещё на этапе разбития на слова.
И дайте мне уже гиперссылку на БД, пожалуйста.
Проверяйте на повторное вхождение слов, набранный массив - ещё на этапе разбития на слова.
Логично, делю размер массива на два, при заполнении. Если делиться нацело, то проверяю на совпадение. То есть в некоторых случаях придётся не весь массив заполнять по словам, а только до уровня, пока сопадений не нашёл. Спасибо.
Есть ещё способы?
И дайте мне уже гиперссылку на БД, пожалуйста.
Уже ответил. Возможно данные нарушают какие нибудь авторские права, мне пока некогда об этом думать. Пока эти данные у меня -- это просто прикол, по вечерам читаю. Когда сделаю чат, подумаю об опен соурсе, узнаю про права.
Я бы делал так же. Но только не половину, а всего 6 слов. Итого перебор у вас будет не более 36.
Вам же всё равно такой проход делать один раз. - задача не параметрическая, оптимизировать нет смысла. А он константный и 3,6 миллиона он займёт не более 36 секунд. А скорее всего менее 1 секунды.
Вам же всё равно такой проход делать один раз. - задача не параметрическая, оптимизировать нет смысла. А он константный и 3,6 миллиона он займёт не более 36 секунд. А скорее всего менее 1 секунды.
Я бы делал так же. Но только не половину, а всего 6 слов
В теории там может быть и 75 слов * 2 (то есть два раза повторяются по 75 слов).
Итого перебор у вас будет не более 36.
Сейчас проверяю орфографию, очень хочу за неделю управиться.
Я пока тоже в начале пути. Только закончил оцифровку данных из тех что планировал. Думаю над тем где найти ещё штук 8 источников.
Я с СУБД не стал работать, решил что она медленная для моих задач. ДА и сейчас мои объёмы текстов всего 150 мб. С учётом того что в память я гружу не всё а только небольшие части. Эта работает очень быстро, правда оптимизацией я не занимался и таки 5 минут в энергосберегающем режиме. Предположу что мои 150 МБ это как 1 миллион ваших строк.
Орфография элементарно проверяется. Ищем все слова и которые встречаются менее заданного порога, те написаны с ошибкой.
Вы же после орфографии сделаете лематизацию и заведёте на каждое слово по номеру. Эта ускорит обработку в 6 раз, а то и более.
Другими словами вначале изучаете объект, а после на него воздействуете.
Вначале оцениваем сколько повторов на не большом кусочке, но вполне достаточном. Если для 1000 строк эта будет маленькая ошибка менее 1 процента то и на большой выборке ошибка будет менее 1 процента. Так что достаточно сделать оценку на 1000 или если хочется на 10 000 сток.
Предложение это обычно не более 6 слов(сложно сочинённые это несколько предложений). Если слова повторяются более чем через 6 слов, то это уже повтор предложений. И их проверку можно сделать от точки или запятой или другого знака препинания.
Я с СУБД не стал работать, решил что она медленная для моих задач. ДА и сейчас мои объёмы текстов всего 150 мб. С учётом того что в память я гружу не всё а только небольшие части. Эта работает очень быстро, правда оптимизацией я не занимался и таки 5 минут в энергосберегающем режиме. Предположу что мои 150 МБ это как 1 миллион ваших строк.
Орфография элементарно проверяется. Ищем все слова и которые встречаются менее заданного порога, те написаны с ошибкой.
Вы же после орфографии сделаете лематизацию и заведёте на каждое слово по номеру. Эта ускорит обработку в 6 раз, а то и более.
Вы неправильно подходите. Нужно как в теории управления есть объект подал на него команду получил по обратной связи реакцию. По реакции подал вторую команду.В теории там может быть и 75 слов * 2
Другими словами вначале изучаете объект, а после на него воздействуете.
Вначале оцениваем сколько повторов на не большом кусочке, но вполне достаточном. Если для 1000 строк эта будет маленькая ошибка менее 1 процента то и на большой выборке ошибка будет менее 1 процента. Так что достаточно сделать оценку на 1000 или если хочется на 10 000 сток.
Предложение это обычно не более 6 слов(сложно сочинённые это несколько предложений). Если слова повторяются более чем через 6 слов, то это уже повтор предложений. И их проверку можно сделать от точки или запятой или другого знака препинания.
Я пока тоже в начале пути.
Может стоит объединиться, хотя бы в почте общаться? Вдвоём будет легче, потом может ещё кто подтянется.
---
Думаю над тем где найти ещё штук 8 источников.
А у вас какой (какие) источники?
Предположу что мои 150 МБ это как 1 миллион ваших строк.
Для первых 10 000 строк у меня длина не очищенной и не проверенной строки: вопрос: 245 и ответ 309 символов. Но база изменится кардинально.
Ищем все слова и которые встречаются менее заданного порога, те написаны с ошибкой.
Может Вы и правы, но у меня совсем ппц. Я сперва программой что смогу исправлю, а потом разбивать буду -- проверю Ваш способ.
Вы же после орфографии сделаете лематизацию и заведёте на каждое слово по номеру.
Не уверен, но попробую.
Другими словами вначале изучаете объект, а после на него воздействуете.
Именно здесь не согласен. Иногда проще обработать все строки, чем высказать какие то предположения и обрабатывать до какого то значения. К тому же в данной ситуации самая време затратная часть алгоритма -- это чтение строки с диска. Обработка на поиск дубликатов, наверное, будет занимать намного меньше времени. Я надеюсь.
Pavia писал(а):Думаю над тем где найти ещё штук 8 источников
сделаете лематизацию: http://www.solarix.ru/for_developers/ap ... -api.shtml
а какова задача?
удалить повторы с сохранением остальной части строки? или игнорировать в дальнейших действиях?
удалить повторы с сохранением остальной части строки? или игнорировать в дальнейших действиях?
удалить повторы с сохранением остальной части строки
Именно это, то есть вместо
с1 с2 с3 с1 с2 с3 с4 с5 с6 с7 с8 с9
с1 с2 с3 с4 с5 с6
с1 с2 с1 с2 с3
записать в базу
с1 с2 с3 с4 с5 с6 с7 с8 с9
с1 с2 с3 с4 с5 с6
с1 с2 с3
зы
Кстати, смотрю курс, умнею. То, что я называл сжатием слов и выделением корня -- это и есть лемматизация. Только для некоторых языков мне придётся стемминг делать (ну или не придётся, там видно будет).
Последний раз редактировалось azsx 07.06.2017 14:27:06, всего редактировалось 1 раз.
понятно, если операция разовая то эффективность неважна, так сойдет.
а то я на фантазировал уже
алгоритмов.
а то я на фантазировал уже
алгоритмов.Операция не совсем разовая. Когда базу заполнять буду, там вообще все алгоритмы по обработке текста понадобятся. Так, что если не жутко сложно пишите или дайте ссылок и терминов.
sts писал(а):если операция разовая то эффективность неважна, так сойдет
))))) +100500