На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Сравнение массивов
    нужно сравнить 2 массива, найти в них одинаковые куски, причем куски могут быть разной длины и в разных частях массива, их может быть разное количество т.е.

    1    2

    A   M
    B   N
    C   A
    X   B
    X   C
    S   Y

    должны найтись куски ABC, их смещения в файлах

    мне приходит в голову только самый простой перебор, вот только на каждый байт одного массива надо просмотреть другой, а это долго уже при 1mb...
      Можно попробовать так:

      1) Сначала составляешь массивы остатков

      a[1] = "ABCXXS"
      a[2] = "BCXXS"
      a[3] = "CXXS"
      a[4] = "XXS"
      a[5] = "XS"
      a[6] = "S"


      b[1] = "MNABCY"
      b[2] = "NABCY"
      b[3] = "ABCY"
      b[4] = "BCY"
      b[5] = "CY"
      b[6] = "Y"

      Разумеется не физически (а то много памяти займет), а всего два массива указателей делаешь a[] и b[]. (O(N) - операций)

      2) Потом каждый их них сортируешь по алфавиту (O(N*log(N)) - операций) (Перетасовываешь указатели)

      3) Ищешь похожие элементы в двух УПОРЯДОЧЕННЫХ массивах.
      a[1] похож на b[3] в первых 3 символах...
      a[2] like b[4] -> 2
      a[3] like b[5] -> 1
      Сложность = O(N*Log(N) + N*g*c), где g - сложность сравнения двух строк, c- коэффициент количества похожих строк 0 < c < 100\%
      Сообщение отредактировано: S.Yu.Gubanov -
         Если немного переделать алгоритм Кнута-Мориса-Пратта, то получится как раз решение задачи.
          А что за алгоритм Кнута-Морриса?
            хехе делал я нечто подобное, и даже дока была крутейшая, правда на наглийском...
            если тебенадо точно, то полный перебор (правда это будет долго)
            если надо быстрее, то
            все решается хеш таблицей за 1, или полтора прохода по каждому из массивов (в моем случае это были 200 мб файлы)  но при этом ессно будут найдены не все одинаковые куски....


            Сообщение отредактировано: Demo_S -
              Цитата AGAMEMNUM, 03.12.02, 16:35:26
              А что за алгоритм Кнута-Морриса?

              http://algolist.manual.ru/search/esearch/kmp.php
              ;D ;D ;D
                В свое время использовал циклический проход одного массива по другому. Т.е. производим сдвиг элементов массива В влево или вправо. И производим сравнение всех элементов обоих массивов. Общее количество операций n2, n - размер массивов
                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                0 пользователей:


                Рейтинг@Mail.ru
                [ Script execution time: 0,0212 ]   [ 15 queries used ]   [ Generated: 21.05.24, 07:22 GMT ]