## page was renamed from Main/HSECompLing/m2012/Solution4 = Разбор задачи = Я не удержусь, и добавлю несколько комментариев / нравоучений по поводу этого примера... == Про etree: == Мне помнится, что из вас почти никто так и не пытался использовать etree, так что прошу вас посмотреть в мою версию, чтобы иметь какое-то представление о том, как оно применяется в жизни. Сравните это с вашими решениями на регулярных выражениях, устыдитесь и проникнетесь тем, мимо какой полезной штуки вы прошли не глядя! (Я не акцентирую ваше внимание на том, что etree сделан в согласии со стандартом XML, и поэтому он никак не зависит от того, где автор какого-нибудь XML-ника решил сделать перенос строки). Попробуйте хотя бы посчитать число строк, которое заняло решение какой-то подзадачки у вас на регулярных выражениях, и сколько строк потребовалось здесь! Дабы проще было разбираться, попробуйте отследить путь переменных: * GUI.xml -- это разобранное в etree дерево всего файла; * GUI.xmls[sentence] -- это словарь, в котором ключ -- текст предложения, значения -- XML-дерево для одного предложения; * Tree.sentence -- это XML-дерево для одного пердложения. == Про преобразование деревьев: == В ваших решениях я наблюдал несколько подходов к решению задачи: как нам перевести деревья из представления, где у каждого узла известен родитель (в котором они в syntagrus), к представлению, в котором у каждого родителя известны дети (которое мы умеем рисовать). Большинство подходов сводились, в конечном счёте, к следующему: мы создаём родителя, а потом проходим по списку всех известных вершин дерева, и если у кого-нибудь данный узел указывался в качестве родителя, то добавляли его в качестве ребёнка. Собственно, мой подход здесь ничем не отличается. Это решение работает за квадратичное время от количества вершин, но так как предложений даже с сотней слов уже почти не бывает (а 100^2 = 10000, что не очень много), то такое время работы вполне приемлемо. Эту задачу можно решать и за линейное время, совсем просто. Предположим, parents -- словарь, в котором по ключу узлу можно получить значение родителя узла. Мы хотим сделать словарь children, в котором по ключу родителю лежит список детей: {{{#!python children = {} for node in parents: parent = parents[node] if parent not in children: children[parent] = [] children[parent].append(node) }}} Доска почёта: Аня Выборнова и Егор Лакомкин изобрели такой же подход. == Про рисование интерфейса: == В лице класса GUI и того, как он запускается, я демонстрирую здесь довольно общепринятый сейчас подход к тому, как делать интерфейсы (что графические, что вебовские -- впрочем, в flask оно выглядит проще). А именно: мы заводим класс (здесь GUI), в котором есть один-несколько методов для рисования (здесь это create_ui*), несколько методов, которые обрабатывают события (здесь это open, search, redraw), и метод run, запуск которого и есть запуск всей программы. Про всякое рисование окошек я здесь показал почти все возможности, которые есть в Tkinter, надеюсь, этот код не выглядит страшным. == Про оформление кода: == Хорошим тоном считается: * чтобы перед каждым определемнием функции или класса оставлять по пустой строке (последование придерживание такой идеи для большинства из вас не характерно); * чтобы название переменной или функции было достаточно информативным и не требовало комментариев (здесь и ко мне есть нарекания; и здесь и у большинства из вас всё хорошо); * чтобы все константы были вынесены наверх и названы содержательным образом; * чтобы код функции всегда укладывался в десять строк (эта константа специфична для питона; для других языков тут правила другие); * чтобы функция, которой предполагается пользоваться только другим функциям того же класса/модуля, начинались с подчёркивания; * чтобы всё, что касается одной темы, было рядом, а всё, что касается разных тем, было далеко * чтобы не было слишком длинных строк (длиннее 70-80 букв). Ещё хорошим тоном считается иметь гораздо больше договорённостей с собой о том, как делать мелочи (чтобы одинаковые вещи всегда делались одинаково) и соблюдать их. Думаю, моё решение вполне можно воспринимать и как пример применения этих идей к жизни. Не нужно стремиться к тому, чтобы ваш код был похож на мой, но я очень рекомендую, чтобы вы старались делать код столь же упорядоченным. Это упрощает чтение кода -- и в первую очередь, вам же самим во время отладки. == Код программы == {{{#!python # coding: utf-8 import Tkinter import tkFileDialog from xml.etree import ElementTree class Tree(object): dx = 25 dy = 25 font = 'Arial' def __init__(self, canvas, sentence, id=None): if id is None: self.word = sentence.find('.//*[@DOM="_root"]') id = self.word.attrib['ID'] else: self.word = sentence.find('.//*[@ID="{0}"]'.format(id)) self.canvas = canvas self.sentence = sentence self.children = [Tree(canvas, sentence, word.attrib['ID']) for word in sentence.findall('.//*[@DOM="{0}"]'.format(id))] def draw(self): self._draw_node(self.dx, self.dy) self._row = [self] while self._row: self._draw_row() self._next_row() def _draw_row(self): max_x = self.dx for parent in self._row: for child in parent.children: child._draw_node(max_x, parent.y1 + self.dy) max_x = child.x1 + self.dx parent._draw_line(child) def _draw_node(self, x, y): self.canvas_id = self.canvas.create_text( (x, y), text=self.word.text, anchor='nw', justify='center', font=self.font, ) self.x0, self.y0, self.x1, self.y1 = self.canvas.bbox(self.canvas_id) def _draw_line(self, child): x0, y0 = (self.x0 + self.x1) / 2, self.y1 x1, y1 = (child.x0 + child.x1) / 2, child.y0 self.canvas.create_line((x0,y0), (x1,y1), arrow='last') def _next_row(self): result = [] for parent in self._row: for child in parent.children: result.append(child) self._row = result class GUI(object): W, H = 500, 500 def __init__(self): self.xmls = {} self.xml = ElementTree.fromstring("<xml/>") self.create_ui() def create_ui(self): self.root = Tkinter.Tk() self.create_ui_top() self.create_ui_middle() self.create_ui_bottom() def create_ui_top(self): top = Tkinter.Frame(self.root) self.query = query = Tkinter.Entry(top) search = Tkinter.Button(top, text="Search", command=self.search) openfile = Tkinter.Button(top, text="Open file", command=self.open) query.pack(side="left", fill="both", expand="yes") search.pack(side="left") openfile.pack(side="left") top.pack(side="top", fill="x") query.bind("<Return>", self.search) def create_ui_middle(self): middle = Tkinter.Frame(self.root) self.sentences = sentences = Tkinter.Listbox(middle) scroll = Tkinter.Scrollbar(middle, command=sentences.yview) sentences['yscrollcommand'] = scroll.set sentences.pack(side="left", fill="both", expand="yes") scroll.pack(side="left", fill="y") middle.pack(side="top", fill="both", expand="yes") sentences.bind("<<ListboxSelect>>", self.redraw) def create_ui_bottom(self): self.canvas = canvas = Tkinter.Canvas(self.root, width=self.W, height=self.H, background="white") canvas.pack(side="top", fill="both", expand="yes") def open(self): file = tkFileDialog.askopenfile() self.xml = ElementTree.parse(file).getroot() def search(self, ev=None): query = self.query.get() self.xmls = {} self.sentences.delete(0, "end") xml_sentences = self.xml.findall(u'.//*[@LEMMA="{0}"]/..'.format(query.upper())) for xml_sentence in xml_sentences: sentence = "".join(word.text + word.tail for word in xml_sentence) sentence = "".join(xml_sentence.itertext()) sentence = sentence.replace("\n", "") self.xmls[sentence] = xml_sentence self.sentences.insert("end", sentence) if not xml_sentences: self.sentences.insert("end", "nothing found") def redraw(self, event): self.canvas.delete("all") sentence = self.sentences.get("active") xml_sentence = self.xmls[sentence] Tree(self.canvas, xml_sentence).draw() def run(self): return self.root.mainloop() if __name__ == "__main__": GUI().run() }}}