Как осуществить поиск похожего текста в MySQL?

#mysql #база_данных #текст #выборка

                    
Дано: таблица с полями id и txt, где txt - небольшая статья, пост или комментарий,
содержащий HTML, примерный объем записи - 2-10 кб, всего записей 100к-1млн.

Нужно извлечь группы записей, в которых текст приблизительно похож, т.е. совпадать
процентов на 80-90, т.к. идентично равных строк в БД нет.

Позволяют ли существующие механизмы БД осуществить такую выборку, и как это сделать?

UPD: (очень близко) есть ли аналог пхп-шного similar_text() в mysql? Скорость выполнения
запроса не имеет значение.
    

Ответы

Ответ 1

Как было сказано выше, можно попробовать расстояние Левенштейна. Еще один пример
реализации для mysql тут: http://www.artfulsoftware.com/infotree/qrytip.php?id=552

Можно сделать адаптированный вариант с этого примера:

CREATE FUNCTION levenshtein( s1 text, s2 text ) 
  RETURNS INT 
  DETERMINISTIC 
  BEGIN 
    DECLARE s1_len, s2_len, i, j, c, c_temp, cost INT; 
    DECLARE s1_char CHAR; 
    -- max strlen=255 
    DECLARE cv0, cv1 VARBINARY(10240); 
    SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2), cv1 = 0x00, j = 1, i
= 1, c = 0; 
    IF s1 = s2 THEN 
      RETURN 0; 
    ELSEIF s1_len = 0 THEN 
      RETURN s2_len; 
    ELSEIF s2_len = 0 THEN 
      RETURN s1_len; 
    ELSE 
      WHILE j <= s2_len DO 
        SET cv1 = CONCAT(cv1, UNHEX(HEX(j))), j = j + 1; 
      END WHILE; 
      WHILE i <= s1_len DO 
        SET s1_char = SUBSTRING(s1, i, 1), c = i, cv0 = UNHEX(HEX(i)), j = 1; 
        WHILE j <= s2_len DO 
          SET c = c + 1; 
          IF s1_char = SUBSTRING(s2, j, 1) THEN  
            SET cost = 0; ELSE SET cost = 1; 
          END IF; 
          SET c_temp = CONV(HEX(SUBSTRING(cv1, j, 1)), 16, 10) + cost; 
          IF c > c_temp THEN SET c = c_temp; END IF; 
            SET c_temp = CONV(HEX(SUBSTRING(cv1, j+1, 1)), 16, 10) + 1; 
            IF c > c_temp THEN  
              SET c = c_temp;  
            END IF; 
            SET cv0 = CONCAT(cv0, UNHEX(HEX(c))), j = j + 1; 
        END WHILE; 
        SET cv1 = cv0, i = i + 1; 
      END WHILE; 
    END IF; 
    RETURN c; 
  END; 

CREATE FUNCTION levenshtein_ratio( s1 text, s2 text ) 
  RETURNS INT 
  DETERMINISTIC 
  BEGIN 
    DECLARE s1_len, s2_len, max_len INT; 
    SET s1_len = LENGTH(s1), s2_len = LENGTH(s2); 
    IF s1_len > s2_len THEN  
      SET max_len = s1_len;  
    ELSE  
      SET max_len = s2_len;  
    END IF; 
    RETURN ROUND((1 - LEVENSHTEIN(s1, s2) / max_len) * 100); 
  END; 


Выбрать попарно похожие строки так:

select t1.id, t1.txt, t2.id, t2.txt
from table1 t1
join table2 t2 on t2.id <> t1.id and levenshtein_ratio(t1.txt, t2.txt) > 80


Как разбить результат выборки на группы, придется подумать.

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

Поэтому я бы рекомендовал, пока не поздно, подумать над тем, чтобы вынести реализацию
за пределы базы. Можно найти множество "быстрых" реализации вычисления расстояния Левенштейна
практически на всех языках. При реализации предложил бы делать какую-то предварительную
фильтрацию, например по длине текста, т.е. если длина не совпадает на 80%, то сравнение
даже не проводить, т.к. даже на производительных машинах сравнение таких объемов текста
уже будет заниматься ощутимое время.


Ответ 2

Вы можете решить данную задачу с помощью использования хранимых процедур.

Например так:

CREATE PROCEDURE dbo.spSimil_FirstNameLastName
   @str1 nvarchar(max),
   @threshold float
AS
SET NOCOUNT ON
SELECT *
FROM (SELECT dbo.fnSimil(@str1, Person.Person.FirstName + N' ' +
Person.Person.LastName) AS Simil, * FROM Person.Person) AS T
WHERE T.Simil >= @threshold
ORDER BY T.Simil DESC;


Процедура вызывается следующим образом:

EXEC dbo.spSimil_FirstNameLastName N'John Adams', 0.75


Подробнее можно узнать тут: http://www.accessmvp.com/tomvanstiphout/simil.htm

Для решения вашей задачи можно попробовать прибегнуть к расстояние Левенштейна:
ссылка на реализацию для mysql: https://github.com/ifsnop/damlev

Несколько результатов из БД, с учётом сортировки

#mysql #sql #база_данных #select #выборка

Имеется таблица book в которой около 50 записей.
Поля таблицы id(int),name(varchar),path(text),lang(int, value = 1,2,3).
lang=1 примерно 18 записей
lang=2 примерно 16 записей
lang=3 примерно 16 записей
Необходимо составить sql запрос, чтобы выбрать 3 книги, первая из которых это случайное
число из первых 18 записей, второе это тоже случайное число из вторых 16 записей, и
третья соответственно тоже случайное число из последних 16 записей

Что то на подобие такого: 
SELECT * FROM book 
            WHERE lang=1 ORDER BY RAND () LIMIT 1 
                                               AND 
            WHERE lang=2 ORDER BY RAND () LIMIT 1
                                               AND 
            WHERE lang=3 ORDER BY RAND () LIMIT 1;
    

Ответы

Ответ 1

Для ваших объемов данных подойдет очень простой запрос:

SELECT random_book.*
FROM book
LEFT JOIN (SELECT * FROM book ORDER BY RAND()) random_book ON (book.lang = random_book.lang)
GROUP BY random_book.lang


ORDER BY RAND() - это не быстро на больших обьемах данных.


Ответ 2

Для ваших объемов:

SELECT * FROM book WHERE lang=1 ORDER BY RAND() LIMIT 1
UNION
SELECT * FROM book WHERE lang=2 ORDER BY RAND() LIMIT 1
UNION
SELECT * FROM book WHERE lang=3 ORDER BY RAND() LIMIT 1


Для больших объемов используйте min(id), max(id), rand() и математику в where - будет
без order by rand

Скорость селекторов jQuery

#jquery #выборка #быстродействие

Подскажите, чем измерить скорость выборки селекторами jQuery? Раньше для FF был java.console,
но, к сожалению, он уже не обновляется, а на новых версиях лисы не пашет.

Нужен именно плагин, а не какой-либо он-лайн сервис.



Решение: Чтобы измерить скорость выборки, пишем в JS коде:

console.time("имя");
выборка с помощью 1 или нескольких селекторов
console.timeEnd("то же имя");


И в консоли Firebug будет писаться время выборки, если между time и timeEnd была
только выборка. Между запуском и остановкой таймера можно запихнуть что угодно, и будет
измеряться, соответственно, общее время выполнения этой части скрипта.

P.S. В DragonFly оперы в консоли также все работает.
    

Ответы

Ответ 1

FireBug думаю поможет


Ответ 2

Самый не удобный и бесполезный способ. В файрфоксе результаты будут отличаться незначительно,
куда интересней измерить скорость различных селекторов в других браузерах, таких как
ие, там выигрыш во времени от оптимизации селекторов будет просто громадным, Можете
посмотреть скорость различных селекторов у всех популярных js-библиотек в тесте slicktest.
Если общей информации не достаточно, можете скачать его и запустить локально, заменив
предложенные селекторы на ваши и тестировать именно на вашем документе. Можно сразу
тестировать везде, а не только в удобном файрбаге.


Ответ 3

Скорость отработки того или иного селектора в значительной мере будет зависеть от
куска DOM на котором его применить.
Чтобы грамотно использовать селекторы нужно понять, как работает движок sizzle, который
и занимается их анализом и парсингом DOM.
Очень хорошо об этом написано тут: http://habrahabr.ru/blogs/jquery/111195/

Выборка среди многих записей SQL

#выборка #sql

К примеру в таблице 1 000 000 записей, как будет вести себя выборка:
SELECT `id` FROM `users` WHERE `group` = '4';

К полю group добавлен индекс.
Чисто для себя узнать. И если медленно, какие способы ускорения существуют? На просторах
интернета толкового так ничего и не нашёл.    

Ответы

Ответ 1

Если group в индексе то на скорость будет влиять только общее количество записей
с group=4 и то это будет влиять на скорость фетча а не на скорость выполнения запроса.


Ответ 2

Добавьте id к индексу по group, чтобы не выполнялась лишняя операция чтения.

Поиск оптимального набора мутация/образцы

#cpp #алгоритм #delphi #выборка #биоинформатика

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


Из общей базы образцов создается выборка по родственным заболеваниям вида:


уникальное_имя_мутации (далее: ИМЯ) количество_заболеваний_вызываемых_этой мутацией
(далее: КОЛВО) список_заболеваний (далее: СПИСОК)

cg26354493  449 1779260,1779264,1779276,1779288,1779303,1779305,1779306,1779312,1779314,1779315,1779321,1779322,1779342,1779437,1779441,1779444,1779469,1779489,1779491,1779497,1779498,1779500,1779501,1779502,1779544,1779545,1779549,1779551,1779553,1779556,1779562,1779594,1779601,1779636,1779638,1779644,1779645,1779647,1899592,1899594,1899596,1899597,1899598,1899622,1899627,1899628,1899629,1899630,1899633,1899635,1899636,1899637,1899638,1899639,1899642,1899643,1899646,1899647,1899648,1899650,1899651,1899657,1899664,1899666,1899740,1899741,1899765,1899766,1899768,1899769,1899770,1899777,1899779,1899780,1899781,1899783,1899784,1899785,1899788,1899789,1899793,1899795,1899798,1899799,1899800,1899801,1899802,1899804,1899805,1899807,1899808,1899810,1899811,1899812,1899816,1899817,1899818,1899820,1899822,1899823,1899824,1899825,1899826,1899827,1899828,1899829,1899830,1899831,1899832,1899833,1899835,1899836,1899839,1899840,1899841,1899842,1899843,1899846,1899847,1899848,1899849,1899851,1899852,1899853,1899857,1899859,1899862,1899863,1899864,1899866,1899868,1899869,1899874,1899875,1899877,1899878,1899880,1899885,1899887,1899889,1899891,1899892,1899896,1899902,1899905,1899909,1899911,1899913,1899916,1899917,1899922,1899924,1899931,1899932,1899933,1899934,1899936,1899937,1899939,1899940,1899942,1899944,1899945,1899963,1899964,1899965,1899966,1899968,1899969,1899970,1899971,1899973,1899975,1899976,1899977,1899978,1899981,1899987,1899990,1899991,1899992,1899994,1899995,1900018,1900019,1900022,1900023,1900024,1900025,1900026,1900027,1900028,1900030,1900031,1900033,1900034,1900035,1900036,1900037,1900047,1900049,1900050,1900051,1900052,1900053,1900057,1900058,1900059,1900060,1900061,1900063,1900065,1900067,1900068,1900069,1900070,1900073,1900074,1900075,1900076,1900078,1900082,1900087,1900088,1900090,1900095,1900098,1900099,1900100,1900101,1900102,1900103,1900104,1900105,1900106,1900109,1900111,1900141,1900142,1900143,1900144,1900152,1900153,1900155,1900156,1900157,1900159,1900160,1900162,1900164,1900165,1900167,1900168,1900169,1900172,1900175,1900176,1900177,1900179,1900181,1900182,1900187,1900188,1900190,1900192,1900194,1900197,1900198,1900200,1900201,1900202,1900203,1900204,1900205,1900206,1900208,1900209,1900210,1900214,1900216,1900217,1900218,1900219,1900226,1900227,1900228,1900229,1900230,1900231,1900232,1900234,1900236,1900237,1900238,1900239,1900240,1900241,1900242,1900243,1900246,1900248,1900249,1900252,1900254,1900255,1900258,2185755,2187686,2187687,2187689,2187690,2187691,2187692,2187693,2187696,2187697,2187699,2187701,2187708,2187709,2187710,2187711,2187713,2187717,2187718,2187719,2187723,2187724,2187726,2187728,2187731,2187732,2187734,2187735,2187736,2187737,2187738,2187739,2187742,2187743,2187745,2187748,2187750,2187751,2187752,2187753,2187754,2187757,2187758,2187759,2187760,2187762,2187763,2187764,2187769,2187771,2187772,2187773,2187774,2187776,2187780,2187781,2187782,2187783,2187784,2187785,2187786,2187787,2187788,2187789,2187792,2187793,2187798,2187799,2187800,2187803,2187805,2187812,2187813,2187815,2187819,2187820,2187821,2187822,2187826,2187827,2187829,2187830,2187831,2187832,2187833,2187835,2187837,2187839,2187840,2187844,2187845,2187848,2187850,2187855,2187857,2187860,2187866,2187868,2187872,2187873,2187874,2187876,2187881,2187882,2187884,2187886,2187887,2187888,2187889,2187894,2187896,2187897,2187898,2262699,2262701,2262702,2262704,2262705,2262706,2262905,2262906,2262910,2263054,2263055,2263056,2263057,2263058,2263162,2263163,2263164,2263244,2263245,2263324,2263325,2339214,2339216,2339217,2339218,2339545,2339547,2339791,2339991,2340135
cg13045134  420 1779257,1779259,1779260,1779264,1779276,1779288,1779300,1779306,1779311,1779312,1779314,1779315,1779322,1779342,1779437,1779439,1779441,1779444,1779445,1779468,1779469,1779487,1779489,1779491,1779493,1779497,1779500,1779501,1779543,1779544,1779545,1779549,1779551,1779553,1779558,1779562,1779578,1779594,1779601,1779607,1779636,1779645,1779647,1899592,1899593,1899595,1899596,1899598,1899622,1899627,1899628,1899629,1899630,1899633,1899635,1899636,1899637,1899638,1899639,1899641,1899643,1899645,1899647,1899648,1899649,1899650,1899651,1899657,1899661,1899662,1899663,1899666,1899668,1899705,1899739,1899764,1899765,1899766,1899767,1899769,1899770,1899777,1899779,1899780,1899781,1899785,1899787,1899788,1899791,1899793,1899795,1899798,1899800,1899801,1899802,1899806,1899808,1899810,1899811,1899812,1899818,1899820,1899822,1899825,1899826,1899829,1899830,1899832,1899833,1899836,1899840,1899841,1899844,1899846,1899847,1899848,1899850,1899851,1899852,1899860,1899862,1899863,1899864,1899866,1899868,1899869,1899870,1899872,1899873,1899874,1899877,1899878,1899880,1899887,1899889,1899891,1899892,1899894,1899901,1899902,1899905,1899909,1899913,1899916,1899917,1899922,1899923,1899924,1899931,1899932,1899933,1899936,1899937,1899938,1899939,1899940,1899941,1899942,1899944,1899945,1899963,1899964,1899965,1899966,1899967,1899968,1899969,1899970,1899971,1899973,1899974,1899976,1899979,1899981,1899983,1899984,1899985,1899986,1899987,1899990,1899991,1899992,1899995,1900018,1900019,1900020,1900023,1900024,1900025,1900026,1900027,1900028,1900029,1900030,1900031,1900032,1900033,1900034,1900035,1900036,1900037,1900047,1900049,1900050,1900052,1900053,1900055,1900059,1900060,1900061,1900062,1900063,1900065,1900066,1900067,1900068,1900069,1900072,1900073,1900074,1900076,1900078,1900079,1900080,1900083,1900086,1900087,1900088,1900089,1900090,1900091,1900093,1900096,1900098,1900100,1900101,1900102,1900103,1900104,1900105,1900106,1900108,1900109,1900110,1900111,1900141,1900142,1900143,1900144,1900154,1900155,1900159,1900162,1900163,1900166,1900167,1900168,1900170,1900172,1900175,1900178,1900184,1900185,1900187,1900188,1900191,1900192,1900194,1900195,1900198,1900199,1900200,1900201,1900202,1900203,1900205,1900208,1900210,1900214,1900218,1900222,1900223,1900225,1900226,1900227,1900229,1900231,1900233,1900234,1900235,1900236,1900237,1900238,1900239,1900240,1900241,1900242,1900243,1900244,1900246,1900248,1900249,1900252,1900254,1900255,1900257,1900258,2185755,2187686,2187687,2187688,2187689,2187694,2187696,2187701,2187708,2187709,2187710,2187711,2187712,2187713,2187717,2187718,2187726,2187727,2187728,2187729,2187730,2187734,2187735,2187737,2187740,2187743,2187744,2187745,2187746,2187747,2187751,2187753,2187754,2187757,2187758,2187761,2187762,2187763,2187764,2187765,2187766,2187769,2187771,2187772,2187773,2187776,2187780,2187782,2187784,2187785,2187786,2187787,2187789,2187792,2187798,2187799,2187800,2187801,2187803,2187807,2187812,2187813,2187815,2187817,2187819,2187820,2187822,2187826,2187827,2187830,2187831,2187833,2187840,2187845,2187846,2187850,2187855,2187857,2187861,2187864,2187865,2187866,2187867,2187868,2187870,2187873,2187874,2187875,2187877,2187882,2187886,2187893,2187894,2187897,2187898,2262699,2262706,2262905,2262909,2263054,2263056,2263057,2263058,2263162,2263164,2263244,2263325,2339214,2339217,2339218,2339548,2339791,2340135
cg18121066  416 1779256,1779257,1779259,1779260,1779264,1779276,1779288,1779300,1779306,1779309,1779312,1779314,1779437,1779439,1779441,1779444,1779469,1779487,1779489,1779491,1779493,1779497,1779500,1779502,1779543,1779544,1779553,1779558,1779562,1779594,1779601,1779607,1779645,1899593,1899594,1899596,1899598,1899622,1899628,1899629,1899630,1899633,1899634,1899636,1899637,1899638,1899639,1899640,1899643,1899647,1899648,1899649,1899650,1899651,1899657,1899661,1899662,1899663,1899665,1899666,1899668,1899739,1899741,1899764,1899766,1899767,1899769,1899770,1899772,1899778,1899779,1899780,1899781,1899782,1899783,1899785,1899787,1899788,1899789,1899791,1899795,1899798,1899800,1899801,1899802,1899804,1899805,1899806,1899807,1899808,1899810,1899811,1899812,1899818,1899820,1899822,1899825,1899826,1899828,1899829,1899830,1899832,1899833,1899836,1899838,1899839,1899843,1899844,1899846,1899847,1899851,1899852,1899860,1899862,1899863,1899864,1899866,1899868,1899869,1899872,1899873,1899874,1899876,1899878,1899880,1899885,1899887,1899889,1899892,1899901,1899902,1899905,1899907,1899909,1899911,1899923,1899924,1899932,1899933,1899934,1899936,1899937,1899938,1899939,1899940,1899941,1899942,1899944,1899945,1899964,1899965,1899966,1899967,1899969,1899970,1899973,1899974,1899976,1899978,1899979,1899980,1899981,1899983,1899984,1899986,1899987,1899990,1899991,1899992,1899995,1900018,1900020,1900023,1900024,1900026,1900027,1900028,1900030,1900031,1900032,1900033,1900034,1900035,1900036,1900047,1900050,1900051,1900052,1900053,1900055,1900056,1900057,1900060,1900061,1900062,1900063,1900064,1900065,1900066,1900067,1900068,1900069,1900070,1900072,1900073,1900076,1900077,1900078,1900079,1900080,1900083,1900085,1900086,1900088,1900089,1900091,1900092,1900093,1900095,1900097,1900100,1900101,1900102,1900103,1900104,1900106,1900108,1900109,1900110,1900111,1900141,1900142,1900143,1900144,1900155,1900156,1900158,1900159,1900160,1900162,1900163,1900164,1900165,1900167,1900168,1900170,1900172,1900173,1900174,1900175,1900176,1900184,1900185,1900187,1900188,1900192,1900194,1900195,1900198,1900199,1900200,1900201,1900202,1900203,1900204,1900205,1900208,1900211,1900212,1900214,1900216,1900222,1900225,1900226,1900228,1900229,1900232,1900233,1900234,1900237,1900238,1900239,1900240,1900241,1900242,1900243,1900244,1900246,1900248,1900249,1900254,1900255,1900258,2185754,2185755,2187686,2187687,2187688,2187692,2187693,2187694,2187696,2187701,2187708,2187709,2187711,2187712,2187718,2187720,2187722,2187727,2187728,2187729,2187730,2187731,2187732,2187733,2187734,2187735,2187736,2187737,2187739,2187740,2187743,2187744,2187745,2187746,2187749,2187751,2187752,2187753,2187754,2187757,2187758,2187760,2187762,2187763,2187764,2187765,2187768,2187769,2187770,2187771,2187772,2187773,2187776,2187781,2187782,2187784,2187786,2187787,2187792,2187793,2187798,2187799,2187800,2187801,2187812,2187813,2187815,2187817,2187819,2187820,2187821,2187822,2187826,2187827,2187829,2187830,2187831,2187834,2187835,2187837,2187838,2187840,2187845,2187846,2187847,2187855,2187857,2187861,2187865,2187866,2187867,2187868,2187873,2187874,2187875,2187877,2187884,2187886,2187894,2187897,2262704,2262706,2262904,2262905,2262906,2262909,2262910,2263054,2263055,2263056,2263057,2263058,2263162,2263164,2263244,2263324,2263325,2339214,2339217,2339218,2339548,2339791,2340135
cg24471254  407 1779255,1779257,1779259,1779260,1779264,1779276,1779288,1779303,1779306,1779309,1779312,1779314,1779315,1779319,1779321,1779322,1779342,1779437,1779439,1779444,1779468,1779469,1779489,1779491,1779493,1779497,1779498,1779501,1779502,1779544,1779545,1779549,1779558,1779562,1779594,1779601,1779636,1779645,1899592,1899594,1899596,1899597,1899598,1899622,1899628,1899629,1899630,1899633,1899634,1899636,1899637,1899638,1899639,1899643,1899647,1899648,1899649,1899650,1899657,1899660,1899661,1899663,1899664,1899668,1899739,1899764,1899765,1899766,1899767,1899769,1899770,1899777,1899778,1899779,1899780,1899781,1899783,1899784,1899785,1899788,1899793,1899795,1899798,1899799,1899800,1899801,1899802,1899804,1899806,1899807,1899808,1899810,1899811,1899812,1899818,1899822,1899823,1899824,1899825,1899826,1899828,1899829,1899831,1899832,1899833,1899836,1899839,1899840,1899844,1899846,1899847,1899848,1899852,1899853,1899857,1899859,1899863,1899864,1899868,1899869,1899873,1899875,1899877,1899880,1899887,1899889,1899890,1899891,1899892,1899901,1899902,1899905,1899909,1899911,1899913,1899916,1899917,1899923,1899924,1899931,1899932,1899933,1899934,1899936,1899937,1899939,1899940,1899941,1899942,1899944,1899945,1899963,1899964,1899965,1899966,1899968,1899969,1899970,1899971,1899974,1899975,1899976,1899977,1899978,1899983,1899984,1899985,1899990,1899991,1899992,1899994,1899995,1900018,1900019,1900021,1900023,1900024,1900025,1900026,1900027,1900028,1900030,1900031,1900032,1900033,1900034,1900035,1900036,1900047,1900049,1900050,1900052,1900053,1900055,1900057,1900059,1900060,1900061,1900063,1900065,1900069,1900070,1900073,1900075,1900080,1900086,1900087,1900088,1900090,1900093,1900095,1900101,1900102,1900103,1900104,1900106,1900108,1900109,1900110,1900111,1900142,1900143,1900144,1900153,1900155,1900156,1900157,1900159,1900160,1900162,1900163,1900164,1900167,1900168,1900172,1900173,1900175,1900176,1900177,1900179,1900180,1900181,1900182,1900186,1900188,1900192,1900195,1900197,1900201,1900202,1900203,1900204,1900206,1900208,1900209,1900211,1900215,1900219,1900222,1900224,1900226,1900228,1900230,1900234,1900237,1900238,1900239,1900240,1900241,1900242,1900243,1900244,1900248,1900249,1900251,1900252,1900255,1900258,2185754,2185755,2187686,2187687,2187688,2187689,2187690,2187691,2187692,2187693,2187694,2187696,2187697,2187701,2187708,2187709,2187710,2187711,2187713,2187715,2187717,2187718,2187719,2187724,2187726,2187727,2187728,2187729,2187731,2187734,2187736,2187737,2187740,2187742,2187743,2187745,2187746,2187751,2187752,2187753,2187754,2187757,2187762,2187763,2187764,2187765,2187766,2187768,2187769,2187771,2187772,2187773,2187776,2187778,2187780,2187781,2187784,2187785,2187786,2187787,2187788,2187792,2187798,2187800,2187801,2187803,2187805,2187807,2187812,2187813,2187815,2187817,2187818,2187820,2187827,2187830,2187831,2187833,2187835,2187837,2187840,2187845,2187846,2187848,2187850,2187855,2187857,2187858,2187861,2187864,2187866,2187868,2187872,2187873,2187875,2187882,2187883,2187886,2187889,2187893,2187896,2187897,2187898,2262699,2262701,2262703,2262705,2262706,2262904,2262905,2262906,2262909,2262910,2263054,2263055,2263056,2263057,2263058,2263162,2263163,2263164,2263245,2263324,2263325,2339214,2339217,2339218,2339547,2340135
cg27317046  390 1779257,1779259,1779264,1779276,1779288,1779303,1779305,1779306,1779309,1779312,1779314,1779315,1779319,1779342,1779437,1779439,1779441,1779444,1779445,1779468,1779469,1779487,1779489,1779491,1779493,1779497,1779500,1779501,1779543,1779544,1779549,1779553,1779558,1779562,1779578,1779594,1779601,1779607,1779636,1779644,1779645,1779647,1899593,1899594,1899596,1899598,1899622,1899627,1899628,1899629,1899630,1899633,1899634,1899635,1899636,1899637,1899639,1899643,1899647,1899648,1899649,1899651,1899657,1899661,1899662,1899663,1899664,1899666,1899668,1899739,1899740,1899741,1899765,1899766,1899770,1899772,1899777,1899779,1899780,1899781,1899782,1899786,1899787,1899788,1899791,1899795,1899798,1899800,1899801,1899802,1899804,1899805,1899806,1899807,1899808,1899812,1899822,1899825,1899826,1899828,1899829,1899830,1899832,1899833,1899836,1899838,1899840,1899841,1899843,1899844,1899846,1899848,1899851,1899860,1899862,1899863,1899864,1899866,1899868,1899869,1899872,1899873,1899874,1899876,1899878,1899880,1899887,1899889,1899891,1899892,1899901,1899902,1899905,1899907,1899909,1899911,1899913,1899916,1899917,1899924,1899931,1899932,1899933,1899934,1899936,1899937,1899940,1899941,1899942,1899944,1899945,1899963,1899964,1899965,1899966,1899968,1899969,1899970,1899971,1899972,1899973,1899974,1899975,1899976,1899977,1899978,1899981,1899983,1899984,1899985,1899990,1899992,1899994,1899995,1900018,1900019,1900020,1900023,1900025,1900026,1900027,1900028,1900029,1900030,1900031,1900032,1900033,1900034,1900035,1900036,1900037,1900047,1900050,1900051,1900052,1900053,1900055,1900056,1900059,1900060,1900062,1900063,1900065,1900066,1900067,1900069,1900070,1900073,1900075,1900076,1900078,1900079,1900081,1900082,1900086,1900088,1900089,1900090,1900101,1900102,1900103,1900104,1900106,1900108,1900109,1900110,1900111,1900142,1900143,1900144,1900155,1900156,1900159,1900162,1900163,1900167,1900168,1900172,1900173,1900174,1900175,1900176,1900181,1900185,1900188,1900192,1900193,1900194,1900195,1900200,1900201,1900202,1900204,1900205,1900206,1900207,1900208,1900209,1900210,1900215,1900216,1900218,1900219,1900220,1900222,1900226,1900228,1900229,1900232,1900234,1900235,1900237,1900238,1900239,1900240,1900241,1900242,1900243,1900246,1900248,1900249,1900252,1900255,1900258,2185754,2187686,2187687,2187688,2187689,2187690,2187691,2187693,2187694,2187708,2187709,2187710,2187711,2187712,2187719,2187728,2187729,2187730,2187731,2187734,2187735,2187737,2187739,2187740,2187743,2187744,2187745,2187746,2187749,2187751,2187753,2187754,2187757,2187761,2187762,2187763,2187764,2187765,2187768,2187769,2187771,2187772,2187773,2187776,2187778,2187781,2187784,2187785,2187786,2187787,2187789,2187792,2187798,2187799,2187800,2187801,2187803,2187812,2187813,2187815,2187819,2187820,2187821,2187822,2187827,2187829,2187830,2187831,2187836,2187837,2187840,2187845,2187847,2187848,2187857,2187866,2187868,2187870,2187873,2187875,2187876,2187886,2187893,2187894,2187897,2262699,2262702,2262704,2262706,2262909,2262910,2263052,2263054,2263055,2263056,2263057,2263058,2263162,2263163,2263164,2263244,2263324,2339214,2339217,2339218,2340135


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

Пример такого файла (выложен кусочек, в котором всего лишь 400 с небольшим строк,
на самом деле, для данной ткани - более 80 тысяч строк,  и для других даже больше).


Необходимо подобрать набор мутаций с числом N (от 8 до 24, в зависимости от того,
какая панель создается), в котором заболевания были бы представлены максимальным числом.
То есть, допустим, мы создаем панель на 16 мутаций, мы выбираем 16 строк, складываем
все заболевания, исключая дубликаты, получаем число заболеваний. Необходимо найти такой
набор из 16 строк, у которого это число было бы максимальным.


Как это делается обычно сейчас.

Обычно лаборатории берут N верхних строк и создают панель на основе такого набора.
Некоторые утруждаются чуть больше, проверяя 2N верхних строк. Как показали пробные
расчёты, можно промахнуться с максимальным числом заболеваний вплоть до 20% (а это много!).

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

Варианты алгоритмов

1. В лоб. Поскольку количество мутаций может достигать сотен тысяч, искать в лоб
будет очень долго. Для рака груди и панели на 24 это, как я понимаю, C из 84372 по
24, будет считаться неизвестно сколько. 

2. Методом группировки. Ищутся пары в которых все заболевания различны. Можно создать
промежуточный файл, который (возможно) пригодится для создания следующей панели. Затем
поиск пар уже среди новых данных. Оценить надежность и эффективность алгоритма не получается :(

3. Методом вычитания. Первая мутация берется "по умолчанию", как указывающая на максимальное
количество заболеваний. Далее с ней по очереди складываются все остальные мутации по
порядку, выбирается пара с максимальным количеством. Теперь с этой парой снова проводится
подобная манипуляция, пока не достигнем N мутаций. Как я понимаю, самый быстрый подход,
но тоже не понятна его надежность.

Есть идеи/решения? 
    

Ответы

Ответ 1

Я бы остановился на варианте 3.
Каждую мутацию мы описываем классом наподобие

class Mutation
{
   std::string name; // Имя мутации
   std::set deseases; // Множество болезней, сопутствующих мутации
}


На первом шаге, после обработки файла мы получим массив мутаций, из которого надо
выбрать N элементов, таким образом, чтобы N элементов содержали максимальное количество
уникальных болезней.
Мне нравится вариант 3, т.к. он даст наиболее 

1) Сортируем массив по размеру множеств болезней. Первый элемент массива, содержащий
максимальное количество болезней выбирается в качестве первого элемента панели.

2) На этом шаге надо рассчитать количество оставшихся уникальных болезней  для каждой
мутации. Т.е. для множество болезней каждой мутации надо сравнить с множеством болезней
панели.
Для с++ это можно сделать функцией std::set_difference. 

3) Добавить элемент с максимальным количеством уникальных элементов к панели. Новое
множество болезней панели будет равно сумме множеств всех входящих в нее мутаций.

4) Пункты 2-3 повторять пока мы не наберем нужное количество элементов или не достигнем
необходимого охвата по болезням (Мы же знаем общее число болезней во всех мутациях
и знаем текущее число болезней в панели)

Минусы:


Поскольку число мутаций может достигать сотен тысяч, процесс расчета панели будет
крайне медленный, т.к. на каждой итерации мы сотни тысяч раз работаем со множествами.


Плюсы:


Точность. Поскольку на каждой итерации мы пересчитываем все множества, то это будет
самый точный способ по охвату уникальных болезней в панели.
Процесс набора панели легкоконтролируем, т.е. на любой итерации мы видим сколько
у нас болезней в панели, сколько осталось и можем приостановить процесс, если достигли
нужной точности (Сомнительный плюс, т.к. остальные способы тоже легко контролируются:)
Результаты вычислений на любом шаге могут быть сохранены для будущих панелей. Процесс
расчета по сути необходим только 1 раз, когда собирается новая панель или обновляется
список мутаций/болезней. Дальше можно использовать заранее рас читанные наборы панелей


P.S.
способ вычисления разницы между множествами можно ускорить за счет оверхэда по размеру
множества, я не знаю как называется этот способ, но суть такова:
Пусть у нас всего существует N болезней, тогда множество болезней конкретной мутации
можно описать как std::vector[N], где N-й элемент вектора обозначает наличие
данной болезни во множестве, т.е. deseases[1779264] = true - обозначает, что множество
содержит болезнь 1779264, а false - не содержит.
Тогда операция вычисления разницы будет выглядеть как поиск всех элементов множества2,
который равны true, но равны false во множестве1.
Операция слияния множеств - битовое или всех элементов.
Возможно это будет быстрее операций над классическими множествами.

P.P.S.
Что-то внутри подсказывает мне, что существует тривиальное решение на SQL, которое
будет сразу выдавать требуемый набор мутаций для панели, но в sql я не силен

Полезные ссылки (по сути у нас всего два метода, слияние множеств и вычисление разницы):
http://www.cplusplus.com/reference/algorithm/set_difference/
http://www.cplusplus.com/reference/algorithm/set_union/

выборка из 3 таблиц с объединением данных

#sql #выборка

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


tm_posts - данные о постах и страницах
tm_attributes - данные о тегах и категориях
tm_relationships - связи 1 и 2 таблицы


Пример структуры:

tm_posts:      

id | name | text
-------------------
1  | kols | <ТЕКСТ>
2  | ando | <ТЕКСТ>
3  | krot | <ТЕКСТ>

tm_attributes:    

id | sign | attr_name
-------------------
1  | tag  | учебник
2  | tag  | дождь
3  | cat  | личное
4  | cat  | опыт

tm_relationships:  

id | id_attr | id_post
-------------------
1  |    1    | 2
2  |    2    | 2
3  |    3    | 2
4  |    4    | 2


Мне нужно получить такой результат по нику ando:

id | name |  text   |      tags     |    category   |
-----------------------------------------------------
2  | ando | <ТЕКСТ> | учебник,дождь |  личное,опыт  |


Т.е. берутся данные из таблицы tm_posts по нику ando, ищется связка тегов и категорий
по id поста в таблице tm_relationships. После чего получаем данные из таблицы tm_attributes.
Эти данные сливаем в строку.

Вот что получилось сделать:

SELECT t1.*, GROUP_CONCAT(t3.attr_name) As `tags`
FROM tm_posts t1
JOIN tm_relationships t2 ON t1.id = t2.id_post
JOIN tm_attributes t3 ON t3.id = t2.id_attr
WHERE t1.name= 'ando'
AND t3.sign = 'tag'
GROUP BY t1.id


Этот код выводит все, кроме категорий. Как мне сюда добавить еще и категории.

-----------------------------Добавлено:

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

Структура таблиц остается такая же.
Результат должен выдать, примерно такой:

id | name |   text  |      tags       |      category     |
----------------------------------------------------------------------
2  | ando | <ТЕКСТ> | учебник,дождь   |       личное      |
5  | ник  | <ТЕКСТ> | какие-то теги   |       личное      |
6  | ник  | <ТЕКСТ> | какие-то теги   |       личное      |


Т.е. выбрались все записи с тегами, но только с определенной категорией "личное"
    

Ответы

Ответ 1

Думаю можно сделать два join к tm_attributes 
наподобие

SELECT t1.*, GROUP_CONCAT(t3.attr_name) As `tags`,GROUP_CONCAT(t4.attr_name) As `cats`
FROM tm_posts t1
JOIN tm_relationships t2 ON t1.id = t2.id_post
left JOIN tm_attributes t3 ON t3.id = t2.id_attr and t3.sign = 'tag'
left JOIN tm_attributes t4 ON t4.id = t2.id_attr and t4.sign = 'cat'
WHERE t1.name= 'ando'

GROUP BY t1.id


Для выбора только категории личное пришел в голову только такой запрос fiddle:

1)  сначала выбираем все Post с категория личное

2) делаем join к категориям

    select cat_data.*, GROUP_CONCAT(t3.attr_name) As `tags` from (select t1.*,t4.attr_name
from tm_attributes t4 
join tm_relationships t2 on id_attr=t4.id 
join tm_posts t1 on id_post=t1.id
where t4.sign = 'cat' and t4.attr_name='личное' ) cat_data
join tm_relationships t2 on id_post=cat_data.id
left JOIN tm_attributes t3 ON t3.id = t2.id_attr and t3.sign = 'tag'
group by cat_data.id


Ответ 2

SELECT t1.*, GROUP_CONCAT(if(t3.sign='tag',t3.attr_name,NULL)) As `tags`,
             GROUP_CONCAT(if(t3.sign='cat',t3.attr_name,NULL)) As `cats`
  FROM tm_posts t1
  JOIN tm_relationships t2 ON t1.id = t2.id_post
  JOIN tm_attributes t3 ON t3.id = t2.id_attr
 WHERE t1.name= 'ando'
   AND t3.sign in('tag','cat')
 GROUP BY t1.id


Условие t3.sign in('tag','cat') можно убрать, если кроме tag и cat нет других видов
и не предвидится. И tm_relationships думаю стоит клеить по LEFT JOIN, в случае, если
у какой то статьи может не быть ни тегов ни категорий.

SQL Выборка по уникальному полю и группировка

Подскажите по выборке повторяющихся значений. Есть таблица
( 1, 'user1', 'Новое сообщение', '2014-02-15' ), ( 2, 'user2', 'Новое сообщение', '2015-05-07' ), ( 3, 'user3', 'Новое сообщение', '2015-09-12' ), ( 4, 'user2', 'Регистрация', '2016-05-16' ), ( 5, 'user1', 'Новое сообщение', '2016-05-16' ), ( 6, 'user4', 'Создание темы', '2016-05-12' )
Как написать запрос, что бы получить сколько юзеров в каждом году написали сообщения впервые,т.е. должно на выходе быть
2014 1 2015 2 2016 0
Если написать данный код
SELECT Extract(YEAR from Date) As Year, Count(DISTINCT user) AS Count FROM table WHERE Type LIKE 'Новое%' GROUP BY Extract(YEAR from Date)
то на выходе будет
Year Count 2014 1 2015 2 2016 1
И я, собственно, понимаю почему так происходит. Как решить данную задачу ?

Ответ

Например так:
Сначала отобрать минимальный номер года, в котором у пользователя появилось новое сообщение, а потом из всего этого сделать группировку с суммированием по годам:
select Year, count(user) as Count from ( select min(extract(YEAR from Date)) as Year, user as User from table where Type like 'Новое%' group by user ) as FirstMessageYears group by Year
Уникальность обеспечивается тем, что мы можем получить только одну минимальную дату для каждого пользователя, так что distinct не понадобится.
Для дополнения строками с годами, по которым есть сообщения, но не первые, можно воспользоваться тем, что count(null) возвращает 0:
Внутренний запрос усложнился тем, что теперь он возвращает года, для которых нет пользователя с первым сообщением, со значение null в колонке пользователя.
select AllYears.Year, count(FirstMessageYears.User) as Count from ( select min(extract(YEAR from Date)) as Year, user as User from table where Type like 'Новое%' group by user ) as FirstMessageYears right join ( select distinct extract(YEAR from Date) as Year from table ) as AllYears on FirstMessageYears.Year = AllYears.Year group by AllYears.Year

Давайте попробуем разобраться. Начинаем "выполнять" SQL запрос "изнутри", т.е. с тех частей, что находятся на максимальном уровне вложенности. В нашем случае, вложенным является сложный подзапрос:
( select min(extract(YEAR from Date)) as Year, user as User from table where Type like 'Новое%' group by user ) as FirstMessageYears right join ( select distinct extract(YEAR from Date) as Year from table ) as AllYears on FirstMessageYears.Year = AllYears.Year

Чтобы понять, что этот подзапрос возвращает, давайте разбирать его на запчасти:
( select min(extract(YEAR from Date)) as Year, user as User from table where Type like 'Новое%' group by user ) as FirstMessageYears
right join
( select distinct extract(YEAR from Date) as Year from table ) as AllYears

Вот, уже немножно легче. Имеем два запроса, каждый возвращает таблицу, потом эти таблицы объединяются посредством операции с непонятным названием right join
Сначала разберёмся, что возвращают каждая из частей перед объединением.
Первый результат подзапроса с красноречивым названием FirstMessageYears будет содержать две колонки: пользователь + дата первого сообщения.
Второй результат подзапроса с названием AllYears будет содержать одну колонку, в которой будут перечислены все года, встречающиеся в исходной таблице table
Что будет, если применить к этим двум наборам операцию right join? Получится таблица, состоящая из двух столбцов, номер года и пользователь. Логически, этот набор заполняется в 2 этапа:
Сначала, в результат объединения попадают те строчки из набора AllYears, для которых нет соответствия в наборе FirstMessageYears. Поле пользователь для этих строчек остаётся null
Потом, в результат объединения попадают те строчки из набора FirstMessageYears, для которых есть соответствие в наборе AllYears. Поле пользователь для этих строчек берётся из набора FirstMessageYears

Остаётся провести по этому результирующему колдовству группировку:
select AllYears.Year, count(FirstMessageYears.User) as Count from [результат выполнения подзапроса] group by Year
а мы помним, что колонка FirstMessageYears.User оказалась со значеним null в тех строчках, которые соответствуют годам, в которые не было первого сообщения от кого-либо из пользователей. Count(null) возвращает 0. Ву-а-ля.

Несколько результатов из БД, с учётом сортировки

Имеется таблица book в которой около 50 записей. Поля таблицы id(int),name(varchar),path(text),lang(int, value = 1,2,3). lang=1 примерно 18 записей lang=2 примерно 16 записей lang=3 примерно 16 записей Необходимо составить sql запрос, чтобы выбрать 3 книги, первая из которых это случайное число из первых 18 записей, второе это тоже случайное число из вторых 16 записей, и третья соответственно тоже случайное число из последних 16 записей
Что то на подобие такого: SELECT * FROM book WHERE lang=1 ORDER BY RAND () LIMIT 1 AND WHERE lang=2 ORDER BY RAND () LIMIT 1 AND WHERE lang=3 ORDER BY RAND () LIMIT 1;

Ответ

Для ваших объемов данных подойдет очень простой запрос:
SELECT random_book.* FROM book LEFT JOIN (SELECT * FROM book ORDER BY RAND()) random_book ON (book.lang = random_book.lang) GROUP BY random_book.lang
ORDER BY RAND() - это не быстро на больших обьемах данных.

Убрать второй или третий знак '!' в строке с помощью регулярного выражения. PHP

Всем привет! Есть строка$string = aaa!bbbb!ccccc!ddddd!eeeeee!ffffff!gggg!...и до бесконечности Мне нужно составить регулярное выражение, меняющее произвольный восклицательный знак на X. Повторений восклицательных знаков через n-e количество символов может быть хоть миллион, поэтому такие варианты:
preg_replace('/^[^!]+/i', 'X', $string); //меняем первый по счету preg_replace('/^([^!]+)(!)([^!])/i', 'X', $string); //меняем второй по счету preg_replace('/^([^!]+)(!)([^!])(!)([^!])/i', 'X', $string); //меняем третий по счету...
...не подходят Подскажите, как сделать такой паттерн(регулярное выражение на выборку), чтобы сменой одной цифры выбирать какой ! менять. Грубо говоря: поставил где-то 1, поменялся первый, поставил 2, поменялся второй и т.д. Спасибо!

Ответ

$text = "aaa!bbbb!ccccc!ddddd!eeeeee!ffffff!gggg!";
$number = 2; $replace = preg_replace ('/!/e',"\$number--==1?'X':'\\0'", $text);
echo $replace;
И с callback для желающих -.-
$text = "aaa!bbbb!ccccc!ddddd!eeeeee!ffffff!gggg!"; $number = 3; $replace = preg_replace_callback('/!/', function ($match) use (&$number) {return $number--==1?'X':$match[0];}, $text); echo $replace;
Результат:
aaa!bbbb!cccccXddddd!eeeeee!ffffff!gggg!

выборка из 3 таблиц с объединением данных

Добрый вечер, имеется проблема, которую никак не могу решить. Существует 3 таблицы:
tm_posts - данные о постах и страницах tm_attributes - данные о тегах и категориях tm_relationships - связи 1 и 2 таблицы
Пример структуры:
tm_posts:
id | name | text ------------------- 1 | kols | <ТЕКСТ> 2 | ando | <ТЕКСТ> 3 | krot | <ТЕКСТ>
tm_attributes:
id | sign | attr_name ------------------- 1 | tag | учебник 2 | tag | дождь 3 | cat | личное 4 | cat | опыт
tm_relationships:
id | id_attr | id_post ------------------- 1 | 1 | 2 2 | 2 | 2 3 | 3 | 2 4 | 4 | 2
Мне нужно получить такой результат по нику ando:
id | name | text | tags | category | ----------------------------------------------------- 2 | ando | <ТЕКСТ> | учебник,дождь | личное,опыт |
Т.е. берутся данные из таблицы tm_posts по нику ando, ищется связка тегов и категорий по id поста в таблице tm_relationships. После чего получаем данные из таблицы tm_attributes. Эти данные сливаем в строку.
Вот что получилось сделать:
SELECT t1.*, GROUP_CONCAT(t3.attr_name) As `tags` FROM tm_posts t1 JOIN tm_relationships t2 ON t1.id = t2.id_post JOIN tm_attributes t3 ON t3.id = t2.id_attr WHERE t1.name= 'ando' AND t3.sign = 'tag' GROUP BY t1.id
Этот код выводит все, кроме категорий. Как мне сюда добавить еще и категории.
-----------------------------Добавлено:
Необходимо выбрать все записи из БД с категорией "личное", но при этом к каждой записи нужно приклеить колонку со связкой тегов.
Структура таблиц остается такая же. Результат должен выдать, примерно такой:
id | name | text | tags | category | ---------------------------------------------------------------------- 2 | ando | <ТЕКСТ> | учебник,дождь | личное | 5 | ник | <ТЕКСТ> | какие-то теги | личное | 6 | ник | <ТЕКСТ> | какие-то теги | личное |
Т.е. выбрались все записи с тегами, но только с определенной категорией "личное"

Ответ

Думаю можно сделать два join к tm_attributes наподобие
SELECT t1.*, GROUP_CONCAT(t3.attr_name) As `tags`,GROUP_CONCAT(t4.attr_name) As `cats` FROM tm_posts t1 JOIN tm_relationships t2 ON t1.id = t2.id_post left JOIN tm_attributes t3 ON t3.id = t2.id_attr and t3.sign = 'tag' left JOIN tm_attributes t4 ON t4.id = t2.id_attr and t4.sign = 'cat' WHERE t1.name= 'ando'
GROUP BY t1.id
Для выбора только категории личное пришел в голову только такой запрос fiddle
1) сначала выбираем все Post с категория личное
2) делаем join к категориям
select cat_data.*, GROUP_CONCAT(t3.attr_name) As `tags` from (select t1.*,t4.attr_name from tm_attributes t4 join tm_relationships t2 on id_attr=t4.id join tm_posts t1 on id_post=t1.id where t4.sign = 'cat' and t4.attr_name='личное' ) cat_data join tm_relationships t2 on id_post=cat_data.id left JOIN tm_attributes t3 ON t3.id = t2.id_attr and t3.sign = 'tag' group by cat_data.id