Hej,
mam taką przykładową listę list słów:
[['rowerowy', 'rower']
['rowerzysta', 'rower']
['domeczek', 'domek']
['domek', 'dom']
['rowerzystka', 'rowerzysta']]
i potrzebuję złączyć wyrazy w grupy zależności, czyli robimy graf połączeń między formami:
rowerowy --> rower <-- rowerzysta <--- rowerzystka
domeczek --> domek --> dom
Jak zostaną nie podpięte do żadnego grafu pary w relacji to one tworzą graf z jedną krawędzią.
Jakieś pomysły ?
Ja bym tak spróbował, żeby przechodząc po każdej parze stworzyć ten graf.
graf mógłby być słownikiem indeksowanym po słowie (np. rower)
jego węzły mogłyby być słownikami z kluczem name (np. rower) oraz kluczem links, gdzie byłaby lista połączeń do innych węzłów
graf mógłbyś stworzyć tak:
dla każdej pary A-B:
sprawdź, czy węzeł dla nazwy A istnieje, jeśli nie istnieje to stwórz go
sprawdź, czy węzeł dla nazwy B istnieje, jeśli nie istnieje to stwórz go
dodaj węzeł A do B['links']
dodaj węzeł B do A['links']
czy to, co mówię, ma sens?
A dlaczego rowerzystka połączona do rowerzysta a nie do rower? Podobnie domeczek do domek a nie do dom? Nie widzę tu jakiejś wyraźnej reguły. Chyba że te grupy mają znaczenie? Ty sam tworzysz te pary czy to masz jakieś gotowe skądś?
Edit:
Pamiętam, że do grafów była w Pythonie taka biblioteka NetworkX. Nie pamiętam już co ona tam dokładnie robiła, ale może zerkniesz sobie na nią.
Prawa to derywat, lewa to baza derywacyjna.
Relacje zawsze idą OD DERYWATU DO BAZY.
Na czym polega problem skoro masz juz pary wierzcholkow, na zbudowanie grafu?
Prostym sposobem jest zamenieniem tej listy na slownik:
lista = [
['rowerowy', 'rower'],
['rowerzysta', 'rower'],
['domeczek', 'domek'],
['domek', 'dom'],
['rowerzystka', 'rowerzysta'],
]
graf = {}
for para in lista:
if para[1] not in graf:
graf[para[1]] = ""
graf[para[0]] = para[1]
print(graf)
print()
print(graf[graf["domeczek"]])
wyjscie:
{'rower': '',
'rowerowy': 'rower',
'rowerzysta': 'rower',
'domek': 'dom',
'domeczek': 'domek',
'dom': '',
'rowerzystka': 'rowerzysta'}
dom
Do czego potrzebujesz tego grafu:
Kolejka na bazarku po ogórki.
-Co Pani podać?
-Poproszę ten grubszy.
-Proszę. A Pani co podać?
-Poproszę ten dłuższy.
-Proszę. A Panu co podać?
-A mi wszystko jedno, mi na sałatkę.
_13th_Dragon napisał(a):
Do czego potrzebujesz tego grafu:
- Wyświetlenia?
- Szukania ścieżek?
- Inne zabawy ...?
Na razie muszę to wypisać.
Potem lengwiści z tym pracują.
ale samo wypisanie moze byc problematyczne, gdy ten graf bedzie bardziej zlozony np taki graf
ab a
ac a
ad a
al a
ala al
all al
to wypisanie go to bedzie jakies:
<- ab
<- ac
a <- ad
ala
<- al <-
all
Suchy702 napisał(a):
ale samo wypisanie moze byc problematyczne, gdy ten graf bedzie bardziej zlozony np taki graf
ab a
ac a
ad a
al a
ala al
all alto wypisanie go to bedzie jakies:
<- ab <- ac a <- ad ala <- al <- all
Nie musi go graficznie wypisać.
Może wypisać listę node'ów (czyli dla grafu który ma 15 node'ów, byłoby 15 linijek), i przy niej wszystkie sąsiednie node'y.
Suchy702 napisał(a):
ale samo wypisanie moze byc problematyczne, gdy ten graf bedzie bardziej zlozony np taki graf
ab a
ac a
ad a
al a
ala al
all al
Ja wypisałbym to następująco (przy dobrej strukturze da się rekurencyjnie):
<- a
<- ad
<- ab
<- ac
<- al
<- ala
<- all
source = \
[
['rowerowy','rower'],
['rowerzysta','rower'],
['domeczek','domek'],
['domek','dom'],
['rowerzystka','rowerzysta'],
]
def showtree(graph,node=None,deep=0):
print(("\t"*deep+"<= " if deep else '')+str(node))
deep+=1
if node in graph:
for sub in sorted(graph[node]):
showtree(graph,sub,deep)
def showtreenoroot(graph,node=None,deep=0):
for sub in sorted(graph[node]):
print(("\t"*deep+"<= " if deep else '')+sub)
if sub in graph:
showtreenoroot(graph,sub,deep+1)
def maketree(source):
graph={}
for pair in source:
nodein,nodeout=pair
if nodeout in graph:
graph[nodeout].add(nodein)
else:
graph[nodeout]={nodein}
graph[None]=set(graph.keys()).difference(set.union(*graph.values()))
return graph
showtree(maketree(source))
print()
showtreenoroot(maketree(source))
print()
showtreenoroot(maketree([['ab','a'],['ac','a'],['ad','a'],['al','a'],['ala','al'],['all','al']]))
Wygląda ok ale przy dużych plikach wywale mi, że za dużo rekurencji :(
Może da się prościej:
ab -> a <- ab <- ac
Paweł Tometczak napisał(a):
Wygląda ok ale przy dużych plikach wywale mi, że za dużo rekurencji :(
Może da się prościej:
ab -> a <- ab <- ac
Czym tobie przeszkadza rekurencja?
Wszystkie przedstawione algorytmy mają złożoność O(1) - tego nie przeskoczysz.
a jeszcze dopytam :-)
mam słownik:
{'odsłuch': ['odsłuchiwać'],
'zgoda': ['zgodzić się', 'zgodzić się', 'godzić'],
'rzeczywisty': ['rzeczywistość', 'rzeczywistość'],
'niezależność': ['niezależny', 'niezależny', 'niezależny'],
'niezależny': ['niezależność', 'niezależność', 'niezależność'],
'mineralny': ['minerał', 'minerał'],
'pociotek': ['pociot'],
'smutny': ['smutek', 'smuta'],
'czerniowiecki': ['Czerniowce'],
'lugrowy': ['lugier'],
'obojętność': ['obojętny', 'obojętny', 'obojętny'],
'szmer': ['szemrać', 'szemrać'],
'akuszerka': ['akuszer', 'akuszerstwo', 'akuszeria']}
Jak najsensowniej wywalić duplikaty z list, które są wartościami słownika ?
set() coś nie idzie:-(
Paweł Tometczak napisał(a):
a jeszcze dopytam :-)
mam słownik:
{'odsłuch': ['odsłuchiwać'], 'zgoda': ['zgodzić się', 'zgodzić się', 'godzić'], 'rzeczywisty': ['rzeczywistość', 'rzeczywistość'], 'niezależność': ['niezależny', 'niezależny', 'niezależny'], 'niezależny': ['niezależność', 'niezależność', 'niezależność'], 'mineralny': ['minerał', 'minerał'], 'pociotek': ['pociot'], 'smutny': ['smutek', 'smuta'], 'czerniowiecki': ['Czerniowce'], 'lugrowy': ['lugier'], 'obojętność': ['obojętny', 'obojętny', 'obojętny'], 'szmer': ['szemrać', 'szemrać'], 'akuszerka': ['akuszer', 'akuszerstwo', 'akuszeria']}Jak najsensowniej wywalić duplikaty w list, które są wartościami słownika ?
set()coś nie idzie:-(
Jeśli słownik jest w zmiennej my_dict, to:
without_duplicates = {key: list(set(value)) for key, value in my_dict.items()}
data = []
with open('extracted_plwn_deriv.tsv') as file:
for line in file.readlines():
if line not in ['\n']:
if not 'GERUNDIUM' in line:
line = line.strip("\n")
a,b,c = line.split("\t")
data.append([c,a])
out. skrócony:
[['odsłuchiwać', 'odsłuch'],
['zgodzić się', 'zgoda'],
['rzeczywistość', 'rzeczywisty'],
['niezależny', 'niezależność'],
['niezależność', 'niezależny'],
['minerał', 'mineralny'],
['pociot', 'pociotek'],
['smutek', 'smutny'],
['Czerniowce', 'czerniowiecki'],
i dalej
graph_group={}
for pair in data:
nodein,nodeout = pair
if nodeout in graph_group:
graph_group[nodeout].append(nodein)
else:
graph_group[nodeout] = [nodein]
graph_group
out:
{'odsłuch': ['odsłuchiwać'],
'zgoda': ['zgodzić się', 'zgodzić się', 'godzić'],
'rzeczywisty': ['rzeczywistość', 'rzeczywistość'],
'niezależność': ['niezależny', 'niezależny', 'niezależny'],
'niezależny': ['niezależność', 'niezależność', 'niezależność'],
'mineralny': ['minerał', 'minerał'],
'pociotek': ['pociot'],
'smutny': ['smutek', 'smuta'],
'czerniowiecki': ['Czerniowce'],
'lugrowy': ['lugier'],
'obojętność': ['obojętny', 'obojętny', 'obojętny'],...
i po usunięciu duplikatów z list
without_duplicates = {key: list(set(value)) for key, value in graph_group.items()}
without_duplicates
out:
{'odsłuch': ['odsłuchiwać'],
'zgoda': ['godzić', 'zgodzić się'],
'rzeczywisty': ['rzeczywistość'],
'niezależność': ['niezależny'],
'niezależny': ['niezależność'],
'mineralny': ['minerał'],
'pociotek': ['pociot'],
'smutny': ['smuta', 'smutek'],
'czerniowiecki': ['Czerniowce'],
'lugrowy': ['lugier'],
'obojętność': ['obojętny'],...
graph_group={}
for pair in data:
nodein,nodeout = pair
if nodeout in graph_group:
graph_group[nodeout].add(nodein) # zmiana 1
else:
graph_group[nodeout] = {nodein} # zmiana 2
graph_group