Performances of an algorithm constructing a nearly optimal binary tree
Identifieur interne : 003821 ( Istex/Checkpoint ); précédent : 003820; suivant : 003822Performances of an algorithm constructing a nearly optimal binary tree
Auteurs : Herman Akdag [France]Source :
- Acta Informatica [ 0001-5903 ] ; 1983-11-01.
English descriptors
- Teeft :
Abstract
Summary: Binary search trees are used in medical diagnostic, species identification, computer decision making, coding, sorting, etc. They are built by applying a sequence of binary tests, when it is required to identify some unknown object or condition, belonging to a given set of possibilities. We search to minimize the path length of a binary tree, giving the probabilities of events. We propose an algorithm which builds the binary tree from the root to the terminal vertices. In this paper, we point out the different properties of that algorithm and the conditions on the probability distribution so that the algorithm becomes nearly optimal.
Url:
DOI: 10.1007/BF00289410
Affiliations:
Links toward previous steps (curation, corpus...)
Links to Exploration step
ISTEX:90DED8EE2F92FD1E540FED39F3EC8150E0758748Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Performances of an algorithm constructing a nearly optimal binary tree</title><author><name sortKey="Akdag, Herman" sort="Akdag, Herman" uniqKey="Akdag H" first="Herman" last="Akdag">Herman Akdag</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:90DED8EE2F92FD1E540FED39F3EC8150E0758748</idno><date when="1983" year="1983">1983</date><idno type="doi">10.1007/BF00289410</idno><idno type="url">https://api.istex.fr/ark:/67375/1BB-2LWTR59D-M/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">002172</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">002172</idno><idno type="wicri:Area/Istex/Curation">002144</idno><idno type="wicri:Area/Istex/Checkpoint">003821</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">003821</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Performances of an algorithm constructing a nearly optimal binary tree</title><author><name sortKey="Akdag, Herman" sort="Akdag, Herman" uniqKey="Akdag H" first="Herman" last="Akdag">Herman Akdag</name><affiliation wicri:level="3"><country xml:lang="fr">France</country><wicri:regionArea>CNRS Groupe de recherche, C.F. Picard, Structures de l'information Université Paris VI, Tour 45, 4, place Jussieu, F-75230, Paris Cédex 05</wicri:regionArea><placeName><region type="region" nuts="2">Île-de-France</region><settlement type="city">Paris Cédex 05</settlement></placeName></affiliation></author></analytic><monogr></monogr><series><title level="j">Acta Informatica</title><title level="j" type="abbrev">Acta Informatica</title><idno type="ISSN">0001-5903</idno><idno type="eISSN">1432-0525</idno><imprint><publisher>Springer-Verlag</publisher><pubPlace>Berlin/Heidelberg</pubPlace><date type="published" when="1983-11-01">1983-11-01</date><biblScope unit="volume">20</biblScope><biblScope unit="issue">2</biblScope><biblScope unit="page" from="121">121</biblScope><biblScope unit="page" to="132">132</biblScope></imprint><idno type="ISSN">0001-5903</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0001-5903</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="Teeft" xml:lang="en"><term>Akdag</term><term>Algorithm</term><term>Binary</term><term>Binary search tree</term><term>Binary tree</term><term>Great probabilities</term><term>Huffman</term><term>Huffman algorithm</term><term>Inequality</term><term>Probability distribution</term><term>Splitting algorithm</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Summary: Binary search trees are used in medical diagnostic, species identification, computer decision making, coding, sorting, etc. They are built by applying a sequence of binary tests, when it is required to identify some unknown object or condition, belonging to a given set of possibilities. We search to minimize the path length of a binary tree, giving the probabilities of events. We propose an algorithm which builds the binary tree from the root to the terminal vertices. In this paper, we point out the different properties of that algorithm and the conditions on the probability distribution so that the algorithm becomes nearly optimal.</div></front></TEI><affiliations><list><country><li>France</li></country><region><li>Île-de-France</li></region><settlement><li>Paris Cédex 05</li></settlement></list><tree><country name="France"><region name="Île-de-France"><name sortKey="Akdag, Herman" sort="Akdag, Herman" uniqKey="Akdag H" first="Herman" last="Akdag">Herman Akdag</name></region></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Istex/Checkpoint
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 003821 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Checkpoint/biblio.hfd -nk 003821 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Istex
|étape= Checkpoint
|type= RBID
|clé= ISTEX:90DED8EE2F92FD1E540FED39F3EC8150E0758748
|texte= Performances of an algorithm constructing a nearly optimal binary tree
}}
| This area was generated with Dilib version V0.6.33. |  |